Approach with Depth-first search
This challenge is similar with previous one: Permutations.
Except for one differient point: there are duplicate elements in array, but we need to return the all unique permutations.
For this purpose, we need to ignore the latter same element during backtraces. First we need to sort the array, then add a check for next valid index:
if(i >=1 && num[i] == num[i-1] && visited[i-1])
continue;
|
class Solution {
public:
void dfs(vector<vector<int> >& res, vector<int>& num,
vector<int> now, vector<int>& visited, int index) {
if(num.size() <= now.size()) {
res.push_back(now);
return;
}
for(int i=0; i < num.size(); i++) {
if(!visited[i]) {
if(i >=1 && num[i] == num[i-1] && !visited[i-1])
continue;
visited[i] = true;
now.push_back(num[i]);
dfs(res, num, now, visited, index+1);
now.pop_back();
visited[i] = false;
}
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
vector<int> now;
vector<int> visited(num.size(), false);
sort(num.begin(), num.end());
if(num.size() == 0) return res;
if(num.size() == 1) {
res.push_back(num);
return res;
}
dfs(res, num, now, visited, 0);
return res;
}
};
|
A trivial optimization
Similar with previous version of Permutations, use in-place approach will also make code simpler:
class Solution {
public:
void dfs(vector<vector<int> >& res, vector<int> num, int index, int end) {
if(index == end-1) {
res.push_back(num);
return;
}
for(int i=index; i < end; i++) {
if(i != index && num[i] == num[index]) continue;
swap(num[index], num[i]);
dfs(res, num, index+1, end);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > res;
sort(num.begin(), num.end());
dfs(res, num, 0, num.size());
return res;
}
};
|
Time complexity: $O(N!)$. 
Preparing for an interview? Check out this!
