Coder's Cat

LeetCode: Permutations II

2020-02-10

Challenge Description

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!)$. file:img/2020_02_10_leetcode-permutations-ii.org_20200210_184542.png

Preparing for an interview? Check out this!