Coder's Cat

LeetCode: Permutations

2020-02-10

Challenge Description

Permutation of A[0..N] equals to:

A[1] + (A[0..N] - A[1])

A[2] + (A[0..N] - A[2])

….

A[N] + (A[0..N] - A[N])

So, the basic idea is using a recursive approach to generate all the permutations.

The time complexity: $O(N!)$.

Here we use vector<bool> used to track which elements used in Depth-Search.

class Solution {
private:
void dfs(vector<vector<int> >& res, vector<int>& num,
vector<bool>& used, vector<int> now) {
if(now.size() == num.size()) {
res.push_back(now);
return;
}
for(size_t k=0; k<used.size(); k++) {
if(used[k]) continue;
used[k] = true;
now.push_back(num[k]);
dfs(res, num, used, now);
now.pop_back();
used[k] = false;
}
}

public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > res;
vector<int> now;
vector<bool> used(num.size(), false);
dfs(res, num, used, now);
return res;
}
};

A trivial improvement with in-place approach

The above code used extra vector<bool> used to track elements usage, this could be avoided with in-place approach. This will save much used memory from stack.

And we even can iterate index which larger than current index:

for (int i = begin; i < num.size(); i++) {
dfs(num, begin + 1, now);
}

So the final code is more simpler and with a better performance:

file:img/2020_02_10_leetcode-permutations.org_20200210_154119.png

class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
dfs(num, 0, result);
return result;
}

void dfs(vector<int> &num, size_t begin, vector<vector<int> > &now) {
if (begin >= num.size()) {
now.push_back(num);
return;
}

for (int i = begin; i < num.size(); i++) {
// in-place current element
swap(num[begin], num[i]);
dfs(num, begin + 1, now);
// reset back
swap(num[begin], num[i]);
}
}
};

Preparing for an interview? Check out this!