Permutations I
Problem Statement (
link):
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Analysis:
A picture worth a thousand words:
Fig. Algorithm demonstration (courtesy of
Yu)
The algorithm is sort of like DFS. We start at the original vector, for each int at index
i, we swap it with each int from index
i to
n, and we move to the next index
i+1 recursively. If we reach the end, we push the result vector to our solution vector. Remember we need to swap back the two entries when getting back to the previous layer.
Code:
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > out;
if (num.empty()) return out;
perm(num, out, 0, num.size());
return out;
}
void perm(vector<int> & num, vector<vector<int> >& out, int idx, int n) {
if (idx==n)
out.push_back(num);
else {
for (int i=idx; i<n; i++) {
swap(num, idx, i);
perm(num, out, idx+1, n);
swap(num, idx, i);
}
}
}
void swap(vector<int> &num, int i, int j) {
int tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
};
Permutations II
Problem Statement (link):
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].
Analysis:
If contains duplicates, the problem is trickier. My initial try was identifying if two swapping ints is same, if not, we swap. But it turns out this yields duplicated result. E.g., we have input 0111, if we swap ints at index 0 and 1, we have 1011; if we swap ints at index 0 and 2, we have 1011.
The condition should be more strict. If we want to swap two ints at index i and j, the idea is to check if any int between i and j are duplicates, if yes, we shouldn't swap as we must have already swapped a same int before. Back to our 0111 example, we could swap ints at index 0 and 1, then we go to swap ints at index 0 and 2, we found two ints at index 1 and 2 are same, then we do not execute the swapping. As a matter of fact, we've already swapped int 0 with int 1 before.
Code:
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int> > out;
if (num.empty()) return out;
sort(num.begin(), num.end()); // sorting for easier identifying duplicates
perm(num, out, 0, num.size());
return out;
}
void perm(vector<int> &num, vector<vector<int> >& out, int idx, int n) {
if (idx==n)
out.push_back(num);
else {
for (int i=idx; i<n; i++) {
if (!containDup(num, idx, i)) { // only swap if no duplicates
swap(num, idx, i);
perm(num, out, idx+1, n);
swap(num, idx, i);
}
}
}
}
bool containDup(vector<int> num, int st, int ed) {
for (int i=st; i<ed; i++)
if (num[i]==num[ed])
return true;
return false;
}
void swap(vector<int> &num, int i, int j) {
int tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
};
