爱悠闲 > DFS 生成所有子集

DFS 生成所有子集

分类: 数据结构与算法  |  作者: zhengkang504 相关  |  发布日期 : 2013-03-19  |  热度 : 1213°

给定一个数组,打印出数组的所有子集。


public class subset {

/**
* @param args
*/
public static int A[] = {1,2,3,4,5};
public static int B[] = {0,0,0,0,0};
public static int total = 0;

public static void main(String[] args) {
// TODO Auto-generated method stub
printSub(5,B,0);
System.out.println("Subset total:"+total);
}

public static void printSub(int n, int[] B, int cur){
if (cur == n){
for (int i = 0; i < n; i++){
if(B[i] == 1){
System.out.print(A[i]);
}
}
total++;
System.out.println();
return;               // 边界处理结束一定要return;
}
B[cur] = 0;
printSub(n,B,cur+1);      // DFS搜索
B[cur] = 1;
printSub(n,B,cur+1);
}
}

输出:


5
4
45
3
35
34
345
2
25
24
245
23
235
234
2345
1
15
14
145
13
135
134
1345
12
125
124
1245
123
1235
1234
12345
Subset total:32