LeetCode 78. 子集

作者:Choi Yang

更新于:7 个月前

字数统计:381 字

阅读时长:1 分钟

题目描述

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

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

示例:

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

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

解题思路

一道组合相关的题目，采用回溯来做即可，题目说明不包含重复元素，于是我们也无需排序然后判断相邻元素是否相等来去重了。

javascript

var subsets = function (nums) {
  let res = [];
  let dfs = (t, start) => {
    res.push(t);
    for (let i = start; i < nums.length; i++) {
      t.push(nums[i]);
      dfs(t.slice(), i + 1);
      t.pop();
    }
  };
  dfs([], 0);
  return res;
};

cpp

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        function<void(vector<int>, int)> dfs = <CustomLink title="&" href="vector<int> t, int start" /> {
            res.push_back(t);
            for (int i = start; i < nums.size(); i++) {
                t.push_back(nums[i]);
                dfs(t, i + 1);
                t.pop_back();
            }
        };
        dfs({}, 0);
        return res;
    }
};

java

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

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

python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(t, start):
            res.append(t[:])
            for i in range(start, len(nums)):
                t.append(nums[i])
                dfs(t, i + 1)
                t.pop()
        dfs([], 0)
        return res

学如逆水行舟，不进则退

Contributors

Choi Yang