LeetCode:Subsets I II(二)
18 {res.push_back(tmpres); return;}
19 int firstSame = iend;
20 while(firstSame >=0 && S[firstSame] == S[iend])firstSame--;
21 firstSame++; //firstSame是第一个和S[iend]相同数字的位置
22 int sameNum = iend - firstSame;//和S[iend]相同数字的个数(除自己)
23 if(sameNum == 0 ||
24 (tmpres.size() >= sameNum && tmpres[tmpres.size() - sameNum] == S[iend]))
25 {
26 //选择S[iend]
27 tmpres.push_back(S[iend]);
28 dfs(S, iend+1, tmpres);
29 tmpres.pop_back();
30 }
31 //不选择S[iend]
32 dfs(S, iend+1, tmpres);
33 }
34 };
复制代码
算法2：在上一题算法2的基础上，如果当前处理的元素没有出现过，则把前面得到的所有集合加上该元素；如果出现过，则只把上一轮处理的集合加上该元素。比如处理第二个2时（二叉树第三层），我们只把上一轮添加过数字的集合{1,2}、{2}再添加一个2加入结果中，{1}、{}是从上一层直接继承下来的，所以不作处理。代码如下：
复制代码
1 class Solution {
2 private:
3 vector >res;
5 vector > subsetsWithDup(vector &S) {
6 // IMPORTANT: Please reset any member data you declared, as
7 // the same Solution instance will be reused for each test case.
8 int len = S.size();
9 sort(S.begin(), S.end());
10 vector > res(1);//开始加入一个空集
11 int last = S[0], opResNum = 1;//上一个数字、即将要进行操作的子集数量
12 for(int i = 0; i < len; ++i)
13 {
14 if(S[i] != last)
15 {
16 last = S[i];
17 opResNum = res.size();
18 }
19 //如果有重复数字，即将操作的子集的数目和上次相同
20 int resSize = res.size();
21 for(int j = resSize-1; j >= resSize - opResNum; j--)
22 {
23 res.push_back(res[j]);
24 res.back().push_back(S[i]);
25 }
26 }
27 return res;
28 }
29 };
复制代码