算法

来源：力扣（LeetCode）90. 子集 II
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

解题思路
这题和昨天那题的区别就在于会包含重复的元素，也就是说[A,B,C] 产生的子集[[],[A],[B],[C],[A,B],[A,C],[C,B],[A,B,C]] 如果B=C 那么[A,C]=[A,B] 题目要求解集不能有重复的元素，那么我们就用set存储结果，就能得到答案了吗？让我们来看这个例子，[2,1,2,2] 产生的子集其中有 [1,2,2] 和[2,1,2] 这两种子集，虽然顺序不同，我们直观就能看出这两个子集是相同的，但是set集合不会认为是相同的。所以为了解决这一问题，我们让初始的集合排序也就是变成[1,2,2,2] 那么接下来产生的子集 就只会是[1,2,2],这样我们就能得到答案了。
昨天的代码我还是不能理解为啥能那样做，虽然直到这样做能得到答案，按我的思路应该是：

放入set集合就好，重复元素一排除就会是结果。但是看上图很巧的是都是树的左节点保留，右节点可以舍去。很巧的是把所有的黄色节点左移填充就会得到昨天的图。很可惜智力不够，尚不能理解透。

代码

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,result,item,res_set);
        return result;
    }
private:
    void generate(int i,vector<int>& nums,vector<vector<int>> &result,
        vector<int> &item,set<vector<int>> &res_set){
            if(i>=nums.size()){
                return;
            }
            item.push_back(nums[i]);
            if(res_set.find(item)==res_set.end()){
                result.push_back(item);
                res_set.insert(item); 
            }
            generate(i+1,nums,result,item,res_set);
            item.pop_back();
            generate(i+1,nums,result,item,res_set);
        }
};

来源：力扣（LeetCode）40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

解题思路
这题解题思路和上题大同小异，最主要的一点就是剪枝，减少遍历的节点。比如1+2+7>8 了这个时候就不用再往下尝试了，或者10>8,这个节点也不需要遍历，当然啦，你也可以在一开始排完数字后，删掉大于target的数。

代码

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        sort(candidates.begin(),candidates.end());
        generate(0,candidates,result,item,res_set,0,target);
        return result;
    }
private:
    void generate(int i,vector<int>& candidates,vector<vector<int>> &result,
        vector<int> &item,set<vector<int>> &res_set,int sum,int target){
            if(sum>=target||i>=candidates.size()||candidates[i]>target){
                return;
            }
            sum+=candidates[i];
            item.push_back(candidates[i]);
            if(sum==target&&res_set.find(item)==res_set.end()){  
                    result.push_back(item);
                    res_set.insert(item);  
            }
            generate(i+1,candidates,result,item,res_set,sum,target);
            sum-=candidates[i];
            item.pop_back();
            generate(i+1,candidates,result,item,res_set,sum,target);
        }
};

最近厌学情绪严重，我慢慢调整下，呜呜呜。