leetcode 链接：子集

题目

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

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

示例：

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

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

解答 & 代码

递归回溯

复杂度分析：

• 时间复杂度：。一个 个状态，每种状态需要 O(n) 的时间来构造子集。

• 空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

  class Solution {
  private:
    void findSubSets(vector<int> nums, int idx, vector<vector<int>>& resultList, vector<int>& result)
    {
        // 递归结束条件：当前下标越界，将当前的 result 存入 resultList
        if(idx >= nums.size())
        {
            resultList.push_back(result);
            return;
        }
  
        // 在子集中放入当前元素，递归
        result.push_back(nums[idx]);
        findSubSets(nums, idx + 1, resultList, result);
        // 回溯，弹出当前元素，即不在子集中放入当前元素，递归
        result.pop_back();
        findSubSets(nums, idx + 1, resultList, result);
    }
  public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> resultList;
        vector<int> result;
        findSubSets(nums, 0, resultList, result);
        return resultList;
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 47.42% 的用户 内存消耗：14.8 MB, 在所有 C++ 提交中击败了 5.02% 的用户 ```