Permutations

Interview Prep

StandardBacktrackingbacktrackingrecursion

The problem

Given an array of distinct integers, return all n! permutations. Order of permutations in the output doesn't matter.

Pattern: backtracking with a "used" set

Subsets and Permutations are the two faces of the backtracking template. In Subsets you advance the input index after each pick; in Permutations you don't advance — every unused element is a candidate at every position. So we need a "used" flag (or, in the swap variant, partition the array into "fixed prefix" and "still available suffix").

Emit only at leaves (when the path has length n), unlike Subsets which emits at every node. That's why Permutations produces n! outputs, while Subsets produces 2^n.

Solution: used-set backtracking

def permute(nums: list[int]) -> list[list[int]]:
    out, path, used = [], [], [False] * len(nums)
    def back():
        if len(path) == len(nums):
            out.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True; path.append(nums[i])
            back()
            path.pop(); used[i] = False
    back()
    return out

Trace

nums = [1, 2, 3]

back([]):
  i=0 (1): back([1]):
    i=1 (2): back([1,2]):
      i=2 (3): back([1,2,3]) -> emit [1,2,3]
    i=2 (3): back([1,3]):
      i=1 (2): back([1,3,2]) -> emit [1,3,2]
  i=1 (2): back([2]):
    i=0 (1): back([2,1]):
      i=2 (3): emit [2,1,3]
    i=2 (3): back([2,3]):
      i=0 (1): emit [2,3,1]
  i=2 (3): back([3]):
    i=0 (1): back([3,1]):
      i=1 (2): emit [3,1,2]
    i=1 (2): back([3,2]):
      i=0 (1): emit [3,2,1]

result (6 permutations): [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

Alternative: in-place swap

A second canonical implementation: instead of a "used" array, keep the array partitioned into a[:start] (a fixed prefix being built) and a[start:] (the still-available multiset). At each step, swap each candidate into position start and recurse with start + 1. Restore the swap on the way back. 

def permute_swap(nums):
    """In-place: at each step, fix one position by swapping in each candidate."""
    out, a = [], nums[:]
    def back(start: int):
        if start == len(a):
            out.append(a.copy()); return
        for i in range(start, len(a)):
            a[start], a[i] = a[i], a[start]
            back(start + 1)
            a[start], a[i] = a[i], a[start]
    back(0)
    return out

Variant: Permutations II (duplicates)

If duplicates are allowed, naive backtracking emits the same permutation many times. Fix: sort the input, then within sibling branches at the same recursion level skip a value if its immediately-previous equal copy is currently unused (meaning a sibling branch will explore that copy in that slot — taking this one would produce a duplicate). 

def permute_unique(nums: list[int]) -> list[list[int]]:
    """Permutations II — handle duplicates by sorting + skipping repeated siblings."""
    nums.sort()
    out, path, used = [], [], [False] * len(nums)
    def back():
        if len(path) == len(nums):
            out.append(path.copy()); return
        for i in range(len(nums)):
            if used[i]: continue
            # skip if this value was already used as the same position's choice
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True; path.append(nums[i])
            back()
            path.pop(); used[i] = False
    back()
    return out

Complexity

Variations worth knowing