46. Permutations

Description

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]
]

My Solution

Source Code

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
30
31
32
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let permute = function(nums) {
  let result = [];
  let arr = [];

  return permuteHelper(nums, arr, result);
};

let permuteHelper = function(choices, currentPermutation, result) {
  if (choices.length === 0) {
    result.push([...currentPermutation]);
  }

  for (let i = 0; i < choices.length; i++) {
    //remove current number from list of choices
    //reminder: since we're backtracking we can't directly modify the choices array in place
    //have to work with a copy
    let newChoices = [...choices.slice(0, i), ...choices.slice(i + 1)];
    //add current to current permutation we're building
    currentPermutation.push(choices[i]);

    permuteHelper(newChoices, currentPermutation, result);

    //when we 'backtrack' up the recursion tree we need to remove the last added number to the current permutation
    currentPermutation.pop();
  }

  return result;
};

Analysis

I'm using recursion for this. I tried an iterative solution first and it got extremely messy extremely quickly. We take an element of the given array and build up a permutation by recursively inserting the remaining elements into the permutation array. The running time for this O(n!) sadly. I can't think of another algorithm that's better than this and I'm not sure there is simply because we're dealing with permutations.