78. 子集

题目

• 题号：78
• 难度：中等
• https://leetcode-cn.com/problems/subsets/

给你一个整数数组nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

示例1

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

实现

思路1 递归

首先定义f(n)计算前n个数的子集，然后我们可以发现以下规律：

• 当n=0时，子集为空集；
• 当n>0时，f(n)=f(n-1)+对f(n-1)的每个子集加入nums[n-1]

解释一下上式：
以示例1为例，nums = [1,2,3]，显然一开始f(0)=[[]]，而当求f(1)时，即求[1]的子集，操作是保留原来f(0)的空集，再复制一个与f(0)一样的结果往里添加nums[0]，也就是新出现的1，此时f(1)=[[],[1]]；当求f(2)时，类似的先保留f(1)的结果，再复制一个之前的结果往里添加新出现的nums[1]=2……因此对前n个数就可以总结为上面的迭代式子。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def getsubs(n, nums):
            res = []
            if n==0:
                res.append([])
                return res
            exist_res = getsubs(n-1, nums)
            res=exist_res[:]
            for subset in exist_res:
                new_subset = subset[:]
                new_subset.append(nums[n-1])
                res.append(new_subset)
            return res
        return getsubs(len(nums), nums)

时间复杂度：
空间复杂度：

思路2 回溯法

这里可以想象成在遍历nums的每个元素构建子集时，每个元素都有被选中和不被选中两种状态（选中就是添加到list中保存最后输出），为此我们可以建立一棵二叉树，然后我们要找到所有叶子节点的情况。那么就可以使用回溯法去遍历。
假设当我们遍历到第i个元素，nums[0, i-1]的数字都是已经确定状态的，而nums[i, n-1]都是未确定状态的。那么此时我们就确定一下nums[i]的状态，即选择加入list保存还是不加入。这里设定为一开始都是加入list的状态，然后nums[i]确定了，就可以递归执行backtrack(i+1, n)，继续重复上述过程来确定nums[i+1]的状态。
上述操作直到遍历到nums的尽头，就会跳出递归，此时开始回溯，也就是把之前加入数组的数字弹出来，然后设定为不加入list的状态，再递归执行backtrack(i+1, n).

class Solution {
public:
    vector<int> t;
    vector<vector<int>> ans;
    void dfs(int cur, vector<int>& nums) {
        if (cur == nums.size()) {
            ans.push_back(t);
            return;
        }
        t.push_back(nums[cur]);
        backtrack(cur + 1, nums);
        t.pop_back();
        backtrack(cur + 1, nums);
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(0, nums);
        return ans;
    }
};

时间复杂度：
空间复杂度：