面试题 08.04. 幂集

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。

示例:

输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

代码思路：

• 每次将res中已存在的List进行复制一份，并将参数中的一个元素添加到每个复制的List中
• 第一步放一个【】空的List进入res中
• 第二次拷贝空的List【】，并放入一个nums形参中的值1，现在res中有【【】，【1】】
• 第三次重复上次的操作，在放入nums中另一个值，res有【【】，【1】，【2】，【1,2】】
• 第三次res中有【【】，【1】，【2】，【1,2】，【3】，【1,3】，【2,3】，【1,2,3】】

代码：

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List> subsets = solution.subsets(new int[]{1, 2, 3});
        System.out.println(subsets.toString());
    }

    public List> subsets(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<>();
        }

        List> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List list = res.get(i);
                ArrayList tmp = new ArrayList<>();
                for (Integer integer : list) {
                    tmp.add(integer);
                }
                tmp.add(num);
                res.add(tmp);
            }
        }
        return res;
    }
}

优化方向：
上面的代码写法时间复杂度是O（n³）…因为我不知道原来ArrayList的构造函数支持直接将另一个ArrayList丢进去
优化一下代码，时间复杂度降到O(n²)

public List> subsets(int[] nums) {
    if (nums.length == 0) {
        return new ArrayList<>();
    }
    List> res = new ArrayList<>();
    res.add(new ArrayList<>());
    for (int num : nums) {
        int size = res.size();
        for (int i = 0; i < size; i++) {
            List list = new ArrayList<>(res.get(i)); 这里不用取出来一个一个遍历来创建一个新List了
            list.add(num);						直接使用Arraylist的构造函数，将需要复制的list丢进去就可以了
            res.add(list);
        }
    }
    return res;
}

性能：
这样时间复杂度就降下来了

解题思路：

• 因为假如数组长度有length，那么它的子集个数就有2^length
• 可以想到用不同的位数来表示不同的子集
• 比如nums为【1,2,3】，那么下面为不同的子集

[0，0，0]   = 【】
[0，0，1]   = 【1】
[0，1，0]   = 【2】
[0，1，1]   = 【1,2】
[1，0，0]   = 【3】
[1，0，1]   = 【1,3】
[1，1，0]   = 【2,3】
[1，1，1]   = 【1,2,3】

代码：

public static List> subsets(int[] nums) {
    //子集的长度是2的nums.length次方，这里通过移位计算
    int length = 1 << nums.length; 
    List> res = new ArrayList<>(length);
    //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
    for (int i = 0; i < length; i++) {
        List list = new ArrayList<>();
        for (int j = 0; j < nums.length; j++) {
            //如果数字i的某一个位置是1，就把数组中对
            //应的数字添加到集合
            if (((i >> j) & 1) == 1)
                list.add(nums[j]);
        }
        res.add(list);
    }
    return res;
}