Permutations

Given an array nums of distinct integers, return every possible ordering (permutation) of its elements.

Each permutation is a list that uses every element of nums exactly once. An array of n distinct values has n! permutations, and your answer must contain each of them exactly once.

The permutations may be returned in any order, but the order of the values within each permutation is, of course, what makes it that permutation.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All values in nums are distinct.

Pattern Path · Backtracking · problem 120 of 169

Start simple

Generate all nⁿ sequences of length n and keep the ones without repeated elements: O(nⁿ · n), far more than the n! answers.

The key idea

A permutation is a sequence of choices: which element goes first, which of the remaining ones goes second, and so on. Backtracking walks that decision tree depth-first. The current path holds the elements chosen so far, and a used array marks which indices are already in the path.

At each level, loop over all indices; skip used ones; for the others, append the value, mark it, recurse to fill the next position, then remove it and unmark it so the next choice starts from the same state. When the path has length n, every element has been placed once, so record a copy.

Because the values are distinct and each level picks a different unused index, every root-to-leaf path is a different ordering and every ordering appears on exactly one path. The tree has n! leaves and copying each finished permutation costs O(n), so the total work is O(n · n!), which is optimal since that is the size of the output.

Complexity

• Time: O(n · n!)
• Space: O(n) besides the output

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result, path = [], []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(path) == len(nums):
                result.append(path[:])  # store a copy
                return
            for i, value in enumerate(nums):
                if used[i]:
                    continue
                used[i] = True
                path.append(value)
                backtrack()
                path.pop()  # undo the choice before trying the next one
                used[i] = False

        backtrack()
        return result

JavaScript

var permute = function(nums) {
  const result = [];
  const path = [];
  const used = new Array(nums.length).fill(false);

  const backtrack = () => {
    if (path.length === nums.length) {
      result.push([...path]); // store a copy
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop(); // undo the choice before trying the next one
      used[i] = false;
    }
  };

  backtrack();
  return result;
};

What the interviewer is checking

It checks that you can write the choose / explore / un-choose backtracking pattern correctly, including restoring state after each recursive call.

Mistakes to avoid

• Appending the shared path list instead of a copy, so every stored permutation is later emptied.
• Forgetting to unmark an element after the recursive call returns.
• Using value in path for the used check: it works but costs O(n) per check.

Follow-ups to expect

• What if nums may contain duplicates? (Sort, skip equal unused neighbours.)
• How do you get the next permutation in lexicographic order? (Find pivot, swap, reverse suffix.)
• How would you find the k-th permutation directly? (Factorial number system.)

In real software

Test generators that try every ordering of operations, brute-force schedulers and puzzle solvers enumerate permutations with exactly this backtracking loop.

Practice next