深度优先搜索解组合问题(JAVA)
题:输出从n不同元素中取m个的所有组合
下面程序使用了深度优先搜索:
public class Combination{
private char a[]; //存储初始字符串
private char r[]; //存储组合结果
public Combination(char[] a){
this.a=a;
r=new char[a.length];
}
//n, 初始字符串的长度
//m, 所求组合的长度
//k, 初始集合中当前处理位置, a[k]
//index 组合的当前长度
void combination(int n, int m, int k, int index){
if(index == m){ //输出组合结果
for(int i = 0; i < m; ++i)
System.out.print(r[i]);
System.out.println();
return;
}
for(int i = k; i < n; ++i){
r[index] = a[i];
combination(n, m, i + 1, index + 1);//注意第三个参数是i + 1
}
}
public static void main(String[] args){
char[] a={'a','b','c','d','e'};
Combination c=new Combination(a);
c.combination(5, 3, 0, 0);
}
}
运行:
D:\tutu>java Combination
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
源码:
