当前位置：网站首页>leetcode:78. 子集

leetcode:78. 子集

2022-07-17 00:51:00 【uncle_ll】

78. 子集

来源：力扣（LeetCode）

链接: https://leetcode.cn/problems/subsets/

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

解法

迭代: 迭代，然后自身遍历加入新的元素
回溯：从空列表开始回溯，每次加入新元素，直到当前层遍历到n时候停止当前层回溯

代码实现

迭代

python实现


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for num in nums:
            newsets = []
            for subset in res:
                new_subset = subset + [num]
                newsets.append(new_subset)
            res.extend(newsets)
        return res

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
           res = res + [[i] + num for num in res]
        return res

c++实现

class Solution {
    
public:
    vector<vector<int>> subsets(vector<int>& nums) {
    
        vector<vector<int>> res;
        res.push_back({
    });
        for(int num: nums) {
    
            vector<vector<int>> newsets;
            for (auto subset: res) {
    
                subset.push_back(num);
                newsets.push_back(subset);
            }
            res.insert(res.end(), newsets.begin(), newsets.end());
        }
        return res;
    }
};

复杂度分析

时间复杂度： $\times 2 ^ n)$
空间复杂度： $O (n)$

回溯

python实现

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def helper(i, tmp):
            res.append(tmp)   # 收集子集，要放在终止添加的上面，否则会漏掉自己
            for j in range(i, n):  # 当j已经大于数组的长度了，就终止了，for循环本来也结束了，所以不需要终止条件
                helper(j+1, tmp+[nums[j]])   # 回溯
        helper(0, [])
        return res

c++实现

class Solution {
    
    vector<vector<int>> res;
public:
    void helper(int i, int n, vector<int> tmp, const vector<int>& nums) {
    
        res.push_back(tmp);
        for(int j=i; j<n; j++) {
    
            tmp.push_back(nums[j]); 
            helper(j+1, n, tmp, nums);
            tmp.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
    
        int n = nums.size();
        helper(0, n, {
    }, nums);
        return res;
    }
};