90.子集II

90.子集II

#回溯 2024-09-07

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
public:

    void backtrace(vector<int>& nums, int cur,bool used){
        result.push_back(path);
        for(int i = cur; i < nums.size(); i++){
            if(i > 0 && nums[i] == nums[i - 1] && used == false){ 	// 判断是否同一层
                continue;
            }            
            path.push_back(nums[i]);
            used = true;
            backtrace(nums,i + 1,used);
            used = false;
            path.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());	// 记得排序
        vector<bool> used(nums.size(),false);
        backtrace(nums,0,used);
        return result;
    }
};

这道题确实再刷没能做出来，但我清楚要去重的是同一层的节点。结合前面已经做的几道题，按理这道就是一个组合题，但可能长时间思考导致思路混乱。这道题卡住我的是 去重，但去重已经在 40.组合总和 II 完成，应该是隔离刷题时间有点久。

有一点你要注意，记得排序，不然我们的去重判断会失败。