https://leetcode.com/problems/subsets-ii/description/ 以 [1,21,22] 为例，若不考虑重复，组合有 [],[1],[1,21],[1,21,22],[1,22],[21],[21,22],[22]. 其中重复的有 [1,22],[22]. 从中我们可以看出只能从重复元素的第一个持续往下添加到列表中，而不能取第二个或之后的重复元素。参考上一题Subsets的模板，能代表「重复元素的第一个」即为 for 循环中的pos变量，i == startIndex 时，i处所代表的变量即为某一层遍历中得「第一个元素」，因此去重时只需判断i != startIndex && s[i] == s[i - 1].
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> subset;
if(nums.size() == 0) return ret;
sort(nums.begin(),nums.end());
dfs(ret,subset,nums, 0);
return ret;
}
private:
void dfs(vector<vector<int>>& ret, vector<int>& subset, vector<int>& nums, int startIndex) {
ret.push_back(subset);
for(int i = startIndex; i<nums.size(); ++i) {
if(i!=startIndex && nums[i]==nums[i-1]) continue;
subset.push_back(nums[i]);
dfs(ret,subset,nums, i+1);
subset.pop_back();
}
}
};