Java求数组所有子数组的两种方法_java 求数组的所有子集

该文参考了其他文章，不过他的实现是用C写的，这里用java

一个包含n个元素的集合,求它的所有子集。比如集合A= {1,2,3}, 它的所有子集是:
{ {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, @}(@表示空集)。

这种问题一般有两种思路，先说说第一种，递归。递归肯定要基于一个归纳法的思想，这个思想用到了二叉树的遍历，如下图所示：

可以这样理解这张图，从集合A的每个元素自身分析，它只有两种状态，或是某个子集的元素，或是不属于任何子集，所以求子集的过程就可以看成对每个元素进行“取舍”的过程。上图中，根结点是初始状态，叶子结点是终结状态，该状态下的8个叶子结点就表示集合A的8个子集。第i层(i=1,2,3…n)表示已对前面i-1层做了取舍，所以这里可以用递归了。整个过程其实就是对二叉树的先序遍历。
代码见方法getSonSet1。

还有一种思想比较巧妙，可以叫按位对应法。如集合A={a,b,c},对于任意一个元素，在每个子集中，要么存在，要么不存在。
映射为子集：
(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->©
(0,0,0)->@(@表示空集)
观察以上规律，与计算机中数据存储方式相似，故可以通过一个整型数与集合映射00…00 ~ 11…11（1表示有，0表示无，反之亦可），通过该整型数逐次增可遍历获取所有的数，即获取集合的相应子集。
实现代码见方法getSonSet2

import java.util.ArrayList;
import java.util.List;

public class SonSet {

	public static void main(String[] args){
		int[] arr={1,2,3};
		
		List<Integer> aList=new ArrayList<Integer>();
		List<Integer> bList=new ArrayList<Integer>();
		for(int i=0;i<arr.length;i++){
			aList.add(arr[i]);
		}
		getSonSet1(0,aList,bList); //方法1，递归法
		
		System.out.println("----数组arr公用，分割线-----");
		
		getSonSet2(arr,arr.length); //方法2，按位对应法
	}

	/*
	 * 递归法
	*/
	public static void getSonSet1(int i,List<Integer> aList,List<Integer> bList){
		if(i>aList.size()-1){
			if(bList.size()<=0){
				System.out.print("@");
			}else {
				/*for(int v:bList){
					System.out.print(v+",");//可以直接用这种方法输出bList数组里所有值，但是每个子数组最后就会带逗号
				}*/
				System.out.print(bList.get(0));
				for(int m=1;m<bList.size();m++){
					System.out.print(","+bList.get(m));
				}
			}
			System.out.println();
		}else {
			bList.add(aList.get(i));
			getSonSet1(i+1, aList, bList);
			int bLen=bList.size();
			bList.remove(bLen-1);
			getSonSet1(i+1, aList, bList);
		}
	}
	
	
	/*
	 *按位对应法。
	*/
	private static void getSonSet2(int[] arr, int length) {
		int mark=0;
		int nEnd=1<<length;
		boolean bNullSet=false;
		for(mark=0;mark<nEnd;mark++){
			bNullSet=true;
			for(int i=0;i<length;i++){
				if(((1<<i)&mark)!=0){//该位有元素输出
					bNullSet=false;
					System.out.print(arr[i]+",");
				}
			}
			if(bNullSet){//空集合
				System.out.print("@");
			}
			System.out.println();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

运行结果：

1,2,3
1,2
1,3
1
2,3
2
3
@
----数组arr公用，分割线-----
@
1,
2,
1,2,
3,
1,3,
2,3,
1,2,3,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17