LeetCode 90 子集 II - 回溯解法

https://leetcode.cn/problems/subsets-ii/description/

和 [组合总和2](LeetCode 40 组合总和 II - 回溯解法.md) 类似.

思路

仍然是从index 到最后选一个数 i 加入path，再从 i 之后到最后选一个数加入到path中,

只不过这里需要去重，方法和 [组合总和2](LeetCode 40 组合总和 II - 回溯解法.md) 一样，这里的重复是for 循环时所取的 loc_nums[i] 与上一个重复了，所以设置 last 标记上一次的选值，当本次选的和上一次选的值重复时就跳过(这里就要求排序了).

last = 11   题目说 数值大小不会超过10, 这里取一个不会取到的值

for(int i = index; i<max;i++){
	if(loc[i]==last)  continue;
	path.push(loc[i])
	add_path(i+1);
	path.pop()
}

代码

class Solution {

public:

    vector<int> loc_nums;

    vector<int> path;

    vector<vector<int>> result;

    void add_path(int index){

        if(path.size()>0) result.push_back(path);

        int last = 11;

        for(int i = index;i<loc_nums.size();i++){

            if(loc_nums[i]==last) continue;

            last = loc_nums[i];

            path.push_back(loc_nums[i]);

            add_path(i+1);

            path.pop_back();

        }

    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        loc_nums = nums;

        sort(loc_nums.begin(), loc_nums.end());

        add_path(0);

        vector<int> tmp;

        result.push_back(tmp);

        return result;

    }

};