幂集

2020-12-31

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

说明：解集不能包含重复的子集。

示例:

 输入： nums = [1,2,3]
 输出：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
通过次数12,028提交次数14,707

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/power-set-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯法

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Set<List<Integer>> resList = new HashSet<>();

        if (nums == null || nums.length == 0) return new ArrayList<>();
        int len = nums.length;
        List<Integer> list = new ArrayList<>();

        resList.add(new ArrayList<>());                                             //空集
        for (Integer val : nums) {
            List<Integer> lst = Arrays.asList(val);
            resList.add(lst);                                                       //包含一个元素的集合
        }
        for (int i = 1; i < len - 1; i++) {
            backtrack(nums, 0, i + 1, resList, new ArrayList<>());
        }
        if (len > 1) {
            for (int i = 0; i < len; i++) {
                list.add(nums[i]);                                                 //包含所有元素的集合
            }
            resList.add(new ArrayList<>(list));
        }
        return new ArrayList<>(resList);
    }
    public void backtrack(int[] nums, int start, int n, Set<List<Integer>> resList, List<Integer> list) {
        if (list.size() == n) {
            resList.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            backtrack(nums, i + 1, n, resList, list);
            list.remove(list.size() - 1);
        }
    }
}

非递归

添加一个空集，结果是[]
访问数字1，对原来的子集追加1，结果是[],[1]
访问数字2，对原来的子集追加2，结果是[],[1],[2],[1,2]
访问数字3，对原来的子集追加3，结果是[],[1],[2],[1,2],[3][1,3],[2,3],[1,2,3]

代码实现如下：

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>(1 << nums.length);
    //先添加一个空的集合
    res.add(new ArrayList<>());
    for (int num : nums) {
        //每遍历一个元素就在之前子集中的每个集合追加这个元素，让他变成新的子集
        for (int i = 0, j = res.size(); i < j; i++) {
            //遍历之前的子集，重新封装成一个新的子集
            List<Integer> list = new ArrayList<>(res.get(i));
            //然后在新的子集后面追加这个元素
            list.add(num);
            //把这个新的子集添加到集合中
            res.add(list);
        }
    }
    return res;
}

优雅的回溯

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
    //走过的所有路径都是子集的一部分，所以都要加入到集合中
    list.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        //做出选择
        tempList.add(nums[i]);
        //递归
        backtrack(list, tempList, nums, i + 1);
        //撤销选择
        tempList.remove(tempList.size() - 1);
    }
}

位运算

nums = [1, 2, 3]，长度为3，取看成是1，不取看成是0.
那么就有：
[0, 0, 0] -> 0
[0, 0, 1] -> 1
[0, 1, 0] -> 2
[0, 1, 1] -> 3
[1, 0, 0] -> 4
[1, 0, 1] -> 5
[1, 1, 0] -> 6
[1, 1, 1] -> 7

把这些0和1看成是二进制，代表0~7共8个数字。幂集大小是2^nums.length。

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        int total = (1 << nums.length);
        for (int i = 0; i < total; ++i) {
            LinkedList<Integer> list = new LinkedList<>();
            int num = i, idx = 0;
            while (num != 0) {
                if ((num & 1) != 0)
                    list.addLast(nums[idx]);
                num >>= 1;
                ++idx;
            }
            res.add(list);
        }
        return res;
    }
}

位运算

public static List<List<Integer>> subsets(int[] nums) {
    //子集的长度是2的nums.length次方，这里通过移位计算
    int length = 1 << nums.length;
    List<List<Integer>> res = new ArrayList<>(length);
    //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
    for (int i = 0; i < length; i++) {
        List<Integer> 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;
}

参考文献

作者：sdwwld来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：gfu 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。