題目

給你一個整數數組 nums ，其中可能包含重復元素，請你返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。返回的解集中，子集可以按 任意順序 排列。
示例 1：
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
輸入：nums = [0]
輸出：[[],[0]]

分析

子集和組合類問題需要用start保證下一次只能選取后面的元素.
但是數據中有重復,需要進行排序和減枝操作.
start為了防止順序不同的相同集合,start+1為了避免重復選擇同一數值.
排序為了把相同的數合在一起,減枝為了防止重復選擇.
算法框架:

選擇列表排序
路徑列表
路徑
void backtrack(選擇列表) {if 路徑 合格:路徑列表.add(路徑)// return 因為子集還能生長if 提前終止:returnfor 選擇 in 選擇列表[start:]:if 選擇 > start && 選擇列表[選擇]==選擇列表[選擇-1]:continue //與前一個相同的樹枝剪掉路徑.add(選擇)backtrack(選擇列表,選擇+1)路徑.pop(選擇) //重新進行下一個選擇
}

C++代碼

class Solution {
private:vector<int> _trace;vector<vector<int>> _results;void backtrack(const vector<int>& nums, const int& start){_results.push_back(_trace);for(int i=start;i<nums.size();i++){if(i>start&& nums[i]==nums[i-1])continue;//減枝_trace.push_back(nums[i]);backtrack(nums, i+1);_trace.pop_back();}}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end(),[](int a,int b){return a<b;});backtrack(nums,0);return _results;}
};