78. 子集

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

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

> 我的解法

class Solution {
private:
    void find_son_depth(vector<int> &nums,int index,int d,int depth){
        if(d > depth) return;
        if(d == depth){
            res.emplace_back(vec);
            return;
        }
        for(int i = index; i < nums.size(); i++){
            vec.emplace_back(nums[i]);
            find_son_depth(nums,i+1,d+1,depth);
            vec.pop_back();
        }        
    }
    void find_son(vector<int> &nums,int depth){
        if(depth == 0) return;
        for(int i = 1; i <= depth; i++){
            find_son_depth(nums,0,0,i);
        } 
    }
public:
    vector<vector<int>> res;
    vector<int> vec;
    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();
        res.resize(1<<len);
        res.clear();
        vec.clear();
        res.emplace_back(vec);
        std::sort(nums.begin(),nums.end());
        find_son(nums,len);
        return res;
    }
};

> 标准解法

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};