Java实现组合（所有子集）的两种方式

举个例子：假设当前数组为 【1,2,3】
那么，用二进制表示就是：

000 : 一个元素都不取
001 ：取数组元素 3
010 ：取数组元素 2
011 ：取数组元素 2,3
100 ：取数组元素 1
101 ：取数组元素 1,3
110 ：取数组元素 1,2
111 ：取数组元素 1,2,3

也就是说，知道使用 for 循环从 0 开始遍历到 2^n - 1（Math.pow(2,nums.length) - 1 ）,然后利用位运算判断每个位置取或者不取即可。

    public void combination(int nums[]) {
        ArrayList temp = new ArrayList<>();
        for (int i = 0; i < Math.pow(2, nums.length); i++) {
            int t = i;
            for (int j = 0; j < nums.length; j++) {
            		//t == 0 表示什么都不取
                if (t == 0) break;
                //判断 t 的最后一位是否为 1
                if ((t & 1) == 1) {
                    //加入倒数第 j 个元素
                    temp.add(nums[nums.length - 1 - j]);
                }
                t >>= 1;
            }
            System.out.println(Arrays.toString(temp.toArray()));
            temp.clear();
        }
    }

[]
[2]
[1]
[2, 1]
[0]
[2, 0]
[1, 0]
[2, 1, 0]

考虑当前位置，每个位置都有选和不选两种情况

    public void combination2(int nums[], ArrayList temp, int curIndex) {
        if (curIndex == nums.length) {
            System.out.println(Arrays.toString(temp.toArray()));
            return;
        }
        //选
        temp.add(nums[curIndex]);
        combination2(nums, temp, curIndex + 1);
        //退选
        temp.remove(temp.size() - 1);

        // 不选
        combination2(nums, temp, curIndex + 1);
    }

[0, 1, 2]
[0, 1]
[0, 2]
[0]
[1, 2]
[1]
[2]
[]