LeetCode78-子集

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/subsets/

中文链接：https://leetcode-cn.com/problems/subsets/

题目详述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

题目详解

DFS，回溯。

  • 首先将当前集合加入到结果集中。

  • 枚举每一个可能的元素。

  • 进入下一层将当前元素加入临时集合中。
  • 递归进入下一层，传入的是当前位置的下一个位置。
  • 恢复原状。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00078 {

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

    private void dfs(int s, int[] nums, List<List<Integer>> res, List<Integer> list) {
        res.add(new ArrayList<>(list));
        for (int i = s; i < nums.length; ++i) {
            list.add(nums[i]);
            dfs(i + 1, nums, res, list);
            list.remove(list.size() - 1);
        }
    }
}

因为是求数组 nums 所有的子集，每个元素有选与不选两种选择，实际上可以直接枚举得到所有的子集。

  • 设 nums 的大小为 n，则子集的个数为 2n。
  • n 个二进制位与 nums 的 n 个元素一一对应。
  • 二进制位为 1，表示选择了对应的元素；二进制位为 0，表示没有选择对应的元素。
  • 从 0 枚举到 2n - 1（每一个子集），把当前数的二进制位上所有 1 对应的元素添加到当前子集中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00078 {

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        int m = 1 << n;
        List<List<Integer>> res = new ArrayList<>(m);
        for (int i = 0; i < m; ++i) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < n; ++j) {
                if (((i >> j) & 1) == 1) {
                    list.add(nums[j]);
                }
            }
            res.add(list);
        }
        return res;
    }
}

还可以从空集开始，通过逐步添加元素的方法来得到所有的子集。

  • 首先在结果集中添加一个空集。
  • 遍历数组 nums。
  • 遍历原来所有的子集，把原来子集拷贝一份，再把当前元素添加入这个子集，得到新的子集。
  • 两重循环完成后，就得到了结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_00078 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(1 << nums.length);
        // 首先添加一个空集
        res.add(new ArrayList<>());
        // 枚举每一个元素
        for (int num : nums) {
            // 枚举原来的每一个子集，把当前元素加入到该子集中
            int size = res.size();
            for (int i = 0; i < size; ++i) {
                // 拷贝一份
                List<Integer> list = new ArrayList<>(res.get(i));
                list.add(num);
                res.add(list);
            }
        }
        return res;
    }
}