求数组的所有子集_求数组子集

比如有数组[1, 2, 3]，其元素数量n = 3，将那么其子集为

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
1
2
3
4
5
6
7
8
9
10

可以用一共三个方法来求出所有子集，以这题作为参考

1.使用二叉树来构建含有子集的叶子节点，然后使用中序遍历

思路

每一层代表一个元素，左子树代表不使用该节点，右子树代表使用该节点，使用中序遍历来获得全部叶子结点，那么就能获得该数组的子集。

思路图

private void getArr(List<Integer> list, List<List<Integer>> result, List<Integer> temp, int level)
    {
        if(level == list.size())
        {
            result.add(temp);
        }
        else
        {
            getArr(list, result, new ArrayList<>(temp), level + 1);
            temp.add(list.get(level));
            getArr(list, result, new ArrayList<>(temp), level + 1);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.使用本质递归法递归遍历

思路

因为这个可以划分出比原问题规模小却同质的问题，那么是可以用递归解决的

private List<List<Integer>> getArr(List<Integer> list, List<List<Integer>> result, int index)
    {
        if(index == list.size())
        {
            result.add(new ArrayList<>());
        }
        else
        {
            List<List<Integer>> arr = new ArrayList<>(getArr(list, result, index + 1));
            for(List<Integer> eList : arr)
            {
                List<Integer> temp = new ArrayList<Integer>(eList);
                temp.add(list.get(index));
                //给子集的每个数组从小到大排序
                temp.sort(Comparator.comparing(Integer::intValue));
                result.add(temp);
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.使用二进制组合遍历

思路

这个最简单，这题有3个元素，假设这三个元素设为连续的二进制数，1代表选取，0代表不选取，从000 - 111一共有八种情况，也是子集的数量。

private void getArr(List<Integer> list, List<List<Integer>> result)
{
	//子集的数量
    int n = 1 << list.size();
    List<Integer> temp = null;
    for(int i = 0; i < n; i ++)
    {
        temp = new ArrayList<>();
        int j = i;
        int index = list.size() - 1;
        //循环前检测j是否是000
        while(j > 0)
        {
            if((j&1) == 1)
            {
                temp.add(list.get(index));
            }
            j = j >> 1;
            index --;
        }
        temp.sort(Comparator.comparing(Integer::intValue));
        result.add(temp);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

经过测试，对于包含元素数量20左右的数组的所有子集，三种方法处理速度都到了1.5-1.8秒左右，到了25之后速度急剧下降，10秒钟也没有结果，因为这三个算法时间复杂度都是O(2^n)级别的

三个算法的思路是参考了这个大佬的博客：
Leetcode:Subsets 求数组的所有子集