Solutions

1. Backtracking

O(n * n!) time | O(n²) space

Intuition

We can grow a tree, where each node holds a partial permutation and every value that is missing from that permutation starts a new branch.

So the root is an empty permutation, with one branch for each element, each holding a permutation of that one value.

When a permutation reaches the size of the input array, it is complete.

Algorithm

Create a permuteFrom function taking the input array, current permutation and result for all complete permutations.
- Add current to result and return when it holds every element.
- Iterate through the loop from the first element to the last element, skipping any value already in current.
- For each element, call permuteFrom again with that value added to current.
Call permuteFrom with an empty current and return the result.

[]

[2]

[2,5]

[2,5,9]

[2,9]

[2,9,5]

[5]

[5,2]

[5,2,9]

[5,9]

[5,9,2]

[9]

[9,2]

[9,2,5]

[9,5]

[9,5,2]

start with [], not taken: 2, 5, 9

1 / 17

Code

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    permuteFrom(nums, [], result)
    return result


def permuteFrom(nums: list[int], current: list[int], result: list[list[int]]) -> None:
    if len(current) == len(nums):
        result.append(current)
        return
    for value in nums:
        if value in current:
            continue
        extended = current + [value]
        permuteFrom(nums, extended, result)

/**
 * @param {number[]} nums
 * @returns {number[][]}
 */
var permute = function (nums) {
  const result = []
  permuteFrom(nums, [], result)
  return result
}

function permuteFrom(nums, current, result) {
  if (current.length === nums.length) {
    result.push(current)
    return
  }
  for (const value of nums) {
    if (current.includes(value)) continue
    const extended = [...current, value]
    permuteFrom(nums, extended, result)
  }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] permute(int[] nums) {
        List<int[]> result = new ArrayList<>();
        permuteFrom(nums, new int[0], result);
        return result.toArray(new int[0][]);
    }

    private void permuteFrom(int[] nums, int[] current, List<int[]> result) {
        if (current.length == nums.length) {
            result.add(current);
            return;
        }
        for (int value : nums) {
            boolean taken = false;
            for (int have : current) {
                if (have == value) taken = true;
            }
            if (taken) continue;
            int[] extended = Arrays.copyOf(current, current.length + 1);
            extended[current.length] = value;
            permuteFrom(nums, extended, result);
        }
    }
}