首页 > 代码库 > leetcode[91] Subsets II
leetcode[91] Subsets II
给定一个数组，返回所有的非重复的可能。例如给定
If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
其实这题类似的有Combination和Subsets。有兴趣的可以看看之前的解题方法。那大概是第70题左右，十天以前做的吧。记得当时用了回溯法。现在这个还是要用到回溯。只是加了判断有重复的子集怎么办。
在回溯的过称中，记录一种可能后就把最后一个pop掉，然后回溯上一个的时候判断是不是和之前判断过的相等了。用一个tmpVal存刚刚pop的数字，如果相等，那就++跳过它。
class Solution {public: void dfs91(vector<vector<int> > &ans, vector<int> &tmp, vector<int> S, int start) { int tmpVal; for (int i = start; i < S.size(); ++i) { tmp.push_back(S[i]); dfs91(ans, tmp, S, i+1); ans.push_back(tmp); tmpVal = tmp[tmp.size()-1]; tmp.pop_back(); while(i+1 < S.size() && tmpVal == S[i+1]) i++; // 跳过和之前pop掉的数字相等的数，因为已经考虑过了 } } vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<int> empty; vector<vector<int> > ans(1,empty); // 空集总是答案之一 sort(S.begin(), S.end()); // 排好序，才符合非降组合 if (S.size()==0) return ans; dfs91(ans, empty, S, 0); return ans; }};
leetcode[91] Subsets II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。