Leetcode#90 Subsets II

跟Subsets（参见这篇文章）类似。

但因为有重复元素，所以要考虑去重问题。

什么情况下会出现重复呢？比如S = {5, 5, 5}，如果要选1个5，一共有C(3,1)=3种选法，即100, 010, 001，这三种情况在集合的角度看是重复的情况。如果要选2个5，共有C(3,2)=3种选法，即011, 101, 110，这三种情况在集合的角度上看也是重复的。

本质在于，如果要在重复出现的数字当中选择若干个，则只能保留一种取法，其他的都是重复。即，这些重复数字对应的二进制位当中，只能保留一个指定若干位为1的数字。前面的例子中，如果要在S种取2个5，则011, 101, 110这三个数字（二进制为都有2个位为1）只能保留一个。保留哪个呢？随便，不过为了方便编码实现，可以保留1都在左边的数字。上面的例子中，保留110。

如果用DFS实现，也是类似的思想，当搜索到某个数字时，如果决定不选了，那么之后同样的数字也都不再选了。（相当于保证1都出现在二进制数字的左边）。

代码（DFS版）：

 vector<vector<int> > res;

 void dfs(vector<int> &S, vector<int> ans, int pos) {

   if (pos == S.size()) {

     res.push_back(ans);

     return;

   }

   ans.push_back(S[pos]);

   dfs(S, ans, ++pos);

   ans.pop_back();

   while (pos < S.size() && S[pos] == S[pos - ])

     pos++;

   dfs(S, ans, pos);

 }

 vector<vector<int> > subsetsWithDup(vector<int> &S) {

   sort(S.begin(), S.end());

   dfs(S, vector<int>(), );

   return res;

 }

巴特西

Leetcode#90 Subsets II

最新文章

热门文章