90. 子集 II

子集 II

原题：

解题方法：

解法一：

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return res;
    }
    void backtracking(vector<int>& nums, int startIdx)
    {
        res.push_back(path);
        for (int i = startIdx; i < nums.size(); i++)
        {
            if (i > startIdx && nums[i] == nums[i - 1] ) {
                continue;
            }
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
        return;
    }
};

做题小结：

和组合总数||一题方法相似，主要难点就在于去重，此处去重的关键在于同层（即for循环内）需要去重，而同枝（即递归内）不需要。

此处i>startIdx很关键，它有效避免了在递归时，也被去重。