2020-10-22每天一刷

力扣90

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subsets-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：本题和之前题的区别在于，原集合中的元素是重复的，结果要求和之前的题相同（不能够含有重复的子集），在上一题上改机即可。首先给原数组的函数排序，然后用回溯法得到每一种子集，再用set对子集的结果进行去重，最后得到想要答案。

class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<int> item; vector<vector<int>> result; set<vector<int>> res_set; sort(nums.begin(),nums.end()); result.push_back(item); generate(0,nums,item,result,res_set); return result; } private: void generate(int i,vector<int>& nums,vector<int>& item, vector<vector<int>>& result, 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,item,result,res_set); item.pop_back(); generate(i+1,nums,item,result,res_set); } };

给定一个数组 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] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路： 回溯法解决问题，通过剪支来降低问题的复杂度。

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