Permutations

Problem

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Requirements

  • duplicates not allowed since distinct

Approach

DFS

  • Use an array of size of input to track when an element is picked
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
  template<std::size_t N>
  void build(const vector<int>& nums, vector<vector<int>>& res, vector<int>& elem,
    bitset<N>& picked) {
    if (elem.size() == nums.size()) {
      res.emplace_back(elem);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      if (picked[i]) continue;
      picked[i] = 1;
      elem.push_back(nums[i]);
      build(nums, res, running, picked);
      picked[i] = 0;
      elem.pop_back();
    }
  }
public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    bitset<nums.size()> picked;
    vector<int> running;
    build(nums, res, running, picked);
    return res;
  }
};

This solution has issues since bitset size needs to be fixed at compile time.

Here is an alternate approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
  template<std::size_t N>
  void build(const vector<int>& nums, vector<vector<int>>& res, vector<int>& elem,
    bool *picked) {
    if (elem.size() == nums.size()) {
      res.emplace_back(elem);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      if (picked[i]) continue;
      picked[i] = true;
      elem.push_back(nums[i]);
      build(nums, res, elem, picked);
      picked[i] = false;
      elem.pop_back();
    }
  }
public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    bool picked[nums.size()] = {false};
    vector<int> running;
    build(nums, res, running, picked);
    return res;
  }
};

So looks like passing arrays needs to be revisited(?)

And the winner is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
  void build(vector<int>& nums,
             vector<vector<int>>& res,
             vector<int>& elem,
            vector<bool>& picked) {
    if (elem.size() == nums.size()) {
      res.emplace_back(elem);
      return;
    }

    for (int i = 0; i < nums.size(); i++) {
      if (picked[i]) continue;
      picked[i] = true;
      elem.push_back(nums[i]);
      build(nums, res, elem, picked);
      picked[i] = false;
      elem.pop_back();
    }
  }
public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<bool> picked(nums.size(), false);
    vector<int> elem;
    build(nums, res, elem, picked);
    return res;
  }
};