子集II
去重分为层次去重和树枝去重
层次去重
是一个元素只能用一次(一样的两个可以用两次,【1,2,2】两个2各自可用一次)。
if (i > indnx && nums[i] == nums[i - 1] ) continue; 当前的和上一个相同就跳过
树枝去重
是数值一样的元素只能用一个,(一样的两个元素也只能用一次。【1,2,2】两个2只能用一个2)
回溯去重
class Solution { public: vector<vector<int>> result; vector<int> path; int pre; void backtracking(vector<int>& nums , int indnx) { result.push_back(path); if(indnx >= nums.size())return; for(int i= indnx ; i < nums.size() ; i++) { if (i > indnx && nums[i] == nums[i - 1] ) { continue; } path.push_back(nums[i]); backtracking(nums , i+1); path.pop_back(); } return; } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); backtracking(nums,0); return result; } };
二刷
class Solution { public: vector<vector<int>> result; vector<int> path; void track_back(vector<int>& nums , int indnx) { if( indnx > nums.size() ) return; result.push_back(path); for(int i =indnx ; i<nums.size() ; i++) { if( i!=indnx && nums[i]==nums[i-1] ) continue; path.push_back(nums[i]); track_back(nums,i+1); path.pop_back(); } return; } vector<vector<int>> subsetsWithDup(vector<int>& nums) { if(nums.size() == 0) return result; sort(nums.begin(),nums.end()); track_back(nums,0); return result; } };