-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPermutationII.cpp
More file actions
38 lines (35 loc) · 1.13 KB
/
PermutationII.cpp
File metadata and controls
38 lines (35 loc) · 1.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
Given a collection of numbers that might contain duplicates, return all possible
unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
*/
class Solution {
public:
//spend some more time try to understand this one
void permuteUtil(vector<vector<int> >& ret, vector<int> perm, vector<int>& num,
vector<bool>& visited) {
if (perm.size() == num.size()) {
ret.push_back(perm);
return ;
}
for (int i = 0; i < num.size(); ++i) {
if (visited[i] ||(i >0 && num[i] == num[i-1] && visited[i-1]) ) continue;
perm.push_back(num[i]);
visited[i] = true;
permuteUtil(ret, perm, num, visited);
perm.pop_back();
visited[i] = false;
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > ret;
if (num.empty()) return ret;
std::sort(num.begin(), num.end());a
vector<bool> visited(num.size(), false);
vector<int> perm;
permuteUtil(ret, perm, num, visited);
return ret;
}
};