LeetCode 90. 子集 II

题目描述

90. 子集 II

解法

我们考虑回溯的方法，但是和 LeetCode 78. 子集 不同的是我们这里需要考虑剪枝的问题，例如对于题目例子 $nums=[1,2,2]$，不剪枝的话生成的结果如下图所示

而正确的结果应该是

所以我们必须有剪枝这一步，体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 $nums[i]==nums[i-1]$，则跳过。具体看下面实现

class Solution {
    
public:
    vector<vector<int>> res;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        vector<int> track;
        backtrace(nums, 0, track);
        return res;
    }

    void backtrace(vector<int>& nums, int start, vector<int> track)
    {
    
        res.push_back(track);

        for (int i = start; i < nums.size(); i++)
        {
    
            if (i > start && nums[i] == nums[i - 1]) continue;
            track.push_back(nums[i]);
            backtrace(nums, i + 1, track);
            track.pop_back();
        }
    }
};