【代码随想录day 24】 力扣 90. 集合II

视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html#%E6%80%9D%E8%B7%AF
力扣题目：https://leetcode.cn/problems/subsets-ii/

其实这道题时78.集合和40.组合总和III的结合体，主要需要注意以下几点：

1. 首先需要将数组排序，方便我们后续操作
2. 子集去重：为了防止找到前面的元素从而输出相同的子集，在遍历过程中应该像78.集合中一样，不要向前遍历，要向后遍历，好马不吃回头草。
3. 数层去重：为了防止数组中重复元素导致的重复子集，我们引入used，used表示每一个数是否使用过的情况，如果相同元素都使用过，说明这个是在同一树枝上的集合，说明这个子集合法，如果发现相同元素时used显示一个用过一个没用过，说明重新开始遍历到了重复元素，所以直接continue掉他
4. 在bool数组的赋值中，可以直接vector used(nums.size(), false);赋值，用for循环力扣会超时报错。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    
    void backtracking(vector<int>& nums, int startIndex, vector<bool>& used)
    {
        //向result数组中存入子集
        result.push_back(path);
        /*
        //判断终止条件
        if(startIndex >= nums.size())
        {
            return;
        }
        */
        //单层搜索
        for(int i = startIndex; i < nums.size(); i++)
        {
            //树层去重
            if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)//如果i>0且nums的i和i-1相等并且没有用过之前的重复元素，说明时新的遍历下的重复元素，剪枝删掉
            {
                continue;
            }
            //存入元素
            path.push_back(nums[i]);
            //更新used
            used[i] = true;
            //回溯算法
            backtracking(nums, i + 1, used);
            //弹出元素
            path.pop_back();
            //更新used
            used[i] = false;

        }
        return;
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //path和result初始化
        path.clear();
        result.clear();
        //used初始化并赋初值
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 去重需要排序
        //执行回溯算法
        backtracking(nums, 0, used);
        //返回结果
        return result;
    }
};