Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
For example,
If nums = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
思路II: 对于重复了n次的字符，可以选择放入0,1,2...n个
class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int>> result; vector<int> pre; if(S.size()==0) return result; sort(S.begin(),S.end()); result.push_back(pre); dfs(S,result,pre,0); return result; } void dfs(vector<int> &S , vector<vector<int>> &result ,vector<int> pre , int depth) { if(depth == S.size()) return; //teminate condition int dupCounter = 0; int dupNum = 0; while(depth+1 < S.size() && S[depth] == S[depth+1]) //get duplicate times { depth++; dupNum++; } while(dupCounter++ <= dupNum) //push duplicate elements { pre.push_back(S[depth]); result.push_back(pre); dfs(S,result,pre,depth+1); } dupCounter = 0; while(dupCounter++ <= dupNum) //backtracking { pre.pop_back(); } dfs(S, result,pre, depth+1); //push none, dfs directly } };
90. Subsets II (Recursion, DP)
原文：http://www.cnblogs.com/qionglouyuyu/p/4855300.html