LeetCode: Permutations

Challenge Description

Approach with Depth-First Search

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!

Join my Email List for more insights, It's Free!😋

← LeetCode: Permutations II LeetCode: Maximum Subarray →