题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例：

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

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

解答 & 代码

递归回溯：
写法一：

class Solution {
private:
    vector<vector<int>> resultList;
    vector<int> curSet;        // 记录回溯算法当前走的路径
    // 回溯算法核心函数，遍历子集问题的回溯树
    // 当前是第 start 层，得到元素个数为 start 的子集
    void backtrack(vector<int>& nums, int start)
    {
        // 前序位置，每个节点的值都是一个子集
        resultList.push_back(curSet);
        // 回溯算法标准框架
        for(int i = start; i < nums.size(); ++i)
        {
            // 做选择
            curSet.push_back(nums[i]);
            // 递归回溯，通过 start 参数控制树枝的遍历，避免产生重复的子集
            backtrack(nums, i + 1);
            // 撤销选择
            curSet.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums, 0);
        return resultList;
    }
};

复杂度分析：设整数数组 nums 有 n 个元素

时间复杂度：n 个元素，每个元素都可以选择放到子集里 or 不放到子集里，一共个状态，每个状态需要 O(n) 的时间构造子集
空间复杂度 O(n)：递归栈空间 = 子集的最大长度

执行结果：

执行结果：通过
执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：7 MB, 在所有 C++ 提交中击败了 60.67% 的用户

写法二：

class Solution {
private:
    vector<vector<int>> resultList;
    vector<int> curSet;
    void backtrack(vector<int>& nums, int start)
    {
        if(start == nums.size())
        {
            resultList.push_back(curSet);
            return;
        }
        curSet.push_back(nums[start]);
        backtrack(nums, start + 1);
        curSet.pop_back();
        backtrack(nums, start + 1);
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums, 0);
        return resultList;
    }
};

执行结果：

执行结果：通过
执行用时：4 ms, 在所有 C++ 提交中击败了 43.03% 的用户
内存消耗：6.8 MB, 在所有 C++ 提交中击败了 90.46% 的用户

hot 100

[中等] 78. 子集

题目

解答 & 代码