Skip to content

LeetCode-78-子集

题目

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

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

示例1:

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

解题思路

方法1、迭代:

外层循环遍历原始数组

内层循环遍历结果集,进行结果集的组合

特例:空集是所有结果的子集

当知道目前结果集有[[],[1]]时,想要得到[1,2]的所有子集,可以通过选择数字2和结果集进行组合得到;2与[]组合,得到[2],2与1组合得到[1,2]。最终结果集为[[],[1],[2],[1,2]]满足数组[1,2]子集结果

在代码上想要进行这类组合,只需要在选择下一个数字后,计算当前结果集的大小,内部循环到size,进行各个位置存的结果的获取,获取之后往尾部添加选择的数字即可。

方法2、回溯:

可以画递归树,看起来更为清晰

回溯的框架:

  • 做出选择
  • 递归进入下一层,此时i+1,从原始数组下一个开始,避免重复选择,所以不需要剪枝
  • 当达到循环结束条件,即数组选完了,撤销上一次选择,走另外的路

Java代码1

java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int num : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> tmp = new ArrayList<>(res.get(i));
                tmp.add(num);
                res.add(tmp);
            }
        }
        return res;
    }
}

Java代码2

java
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) return res;
        List<Integer> path = new ArrayList<>();
        backtrack(nums, 0, path, res);
        return res;
    }

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