Subsets II解题报告

Description:

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice:

Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.

Example:

If S = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]

Link:

http://www.lintcode.com/en/problem/subsets-ii/#

解题方法：

同样是DFS, 只是需要多一个去重步骤。

Tips:

去重代码：
if(i != start && S[i] == S[i-1]) continue;
当循环时碰到与上一个相同的元素直接continue

完整代码：

vector<vector<int> > result; vector<vector<int> > subsetsWithDup(const vector<int> &S) { if(S.size() == 0) { result.push_back({}); return result; } vector<int> source = S; sort(source.begin(), source.end()); vector<int> temp; helper(source, temp, 0); return result; } void helper(const vector<int> &S, vector<int> &temp, int start) { result.push_back(temp); for(int i = start; i < S.size(); i++) { if(i != start && S[i] == S[i-1]) continue; temp.push_back(S[i]); helper(S, temp, i+1); temp.pop_back(); } return; }