Day68 代码随想录打卡|回溯算法篇---子集

题目（leecode T78）：

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

子集（幂集）。

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

方法：本题为求子集问题，采用回溯算法解决，与之前的组合与分割问题我们最后收集的是树上的叶子节点不同。子集问题我们需要收集的是树上的所有节点。且由于自己是无序的，所以我们不能重复选取元素，需要用到startIndex辅助下一次选取的元素的位置。分析回溯三部曲：
1：传入参数与返回值：输入包含数字的字符数组，还有控制位置的startIndex

2：终止条件：当能够选取的数组集合中的元素为空时就停止了，因为我们已经找到了能够选取的所有情况，即startIndex>=nums.size()时停止，但这句其实可以不加，因为我们for循环控制的startIndex本来就不会超过数组的长度

3：单层递归逻辑：自己问题的单层处理比较简单，只需要进入下一个元素，递归然后再回溯即可。

题解：

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    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;
    }
};