LeetCode 46 · Backtracking

Permutations, explained with a picture

Every way to seat guests in a row of chairs.

MediumBacktracking
▶ Watch it step by step

The problem

Given distinct numbers, return every possible ordering (permutation) of them.

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

Picture it

Picture seating guests in a row of chairs. For the first chair, any guest can sit. For the next chair, any guest not yet seated, and so on. The decision tree branches on “who sits next?”. When every chair is filled we write the seating down, then stand the last guest back up and try someone else.

How to recognise it

  • The answer is every ordering of the input, so order matters (unlike subsets and combinations).
  • Every item must be used exactly once in each answer.
  • The input is tiny: at most 6 distinct numbers, giving at most 6! = 720 answers.
  • The decision tree has a different number of branches at each level: n choices for the first position, n − 1 for the second, and so on.
  • Because earlier choices remove options for later ones, you need a way to know what is already used. That is the core of backtracking for arrangements: choose an unused item, recurse, then give it back.

Start with brute force

Fill each of the n positions with any of the n numbers, then keep only the fillings that use every number once.

from itertools import product

def permute_brute(nums):
    n = len(nums)
    return [list(t) for t in product(nums, repeat=n)
            if len(set(t)) == n]

This builds n^n candidate tuples, but only n! of them are real permutations. For n = 6 that is 6^6 = 46,656 candidates for 720 answers, and for n = 6 it still runs in a blink. The gap grows fast, though: for n = 10 it would be 10^10 candidates for 3,628,800 answers. Time is O(n · n^n) and space is O(n) beyond the output.

From brute force to the idea

  1. Find the waste. The brute force happily writes [1, 1, 2] and only throws it away at the end. Most of the n^n candidates are rejected after being fully built.
  2. Reject early. Build one position at a time. Before placing a number, check it is not already in the partial answer.
  3. Keep one shared partial answer. seat is the list built so far. Appending a number seats a guest in the next chair.
  4. Recurse, then undo. After dfs() explores all arrangements of the remaining chairs, seat.pop() stands the guest up, so the next candidate starts from the same state.
  5. Stop when full. When len(seat) == len(nums) every chair is filled; save a copy seat[:].

This is the key idea: build the arrangement one chair at a time, skipping used numbers, and undo each choice after exploring it.

The key idea

Backtracking with a “used” set: choose, recurse, un-choose. n! orderings.

Python solution

def permute(nums):
    res, seat = [], []
    def dfs():
        if len(seat) == len(nums):
            res.append(seat[:]); return
        for x in nums:
            if x not in seat:            # guest still standing
                seat.append(x)
                dfs()
                seat.pop()               # stand up again, try someone else
    dfs()
    return res

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (all n^n fillings)O(n · n^n): build and test each candidateO(n) beyond the output
Backtracking (shown code)O(n² · n!): about n! leaves, and each node loops n times with an O(n) in check on a listO(n) beyond the output: the recursion and seat

The x not in seat test scans a list. A set (or a list of booleans) for "used" would make each check O(1) and bring the time down to O(n · n!).

Edge cases

  • One number ([1]): returns [[1]].
  • Three numbers ([1, 2, 3]): returns the six orderings in the example, in that order.
  • Empty list: returns [[]], the one empty arrangement.
  • Duplicates in the input ([1, 1, 2]): the x not in seat test treats the two 1s as the same, so the seat never fills and the code returns []. The problem promises distinct numbers.
  • Values: negative numbers and zero are fine, as long as they are distinct.
  • Maximum size: 6 numbers produce 720 lists, and the recursion is 7 calls deep.

Common mistakes

  • Forgetting seat.pop(). Only the first arrangement is found: permute([1, 2, 3]) returns just [[1, 2, 3]].
  • Appending seat instead of seat[:], so every result ends up as the same emptied list.
  • Starting the loop at a growing index, as in subsets. That finds combinations, not arrangements, because order is lost.
  • Checking x not in seat by position, not by value, which breaks when values repeat.
Your turn: permutations with repeated numbers

The input may now contain duplicates (for example [1, 1, 2]). Return every distinct ordering, with no repeated lists. Describe your approach, then write it if you like.

Compare with our answer

Track how many copies of each value are still unused, not which positions were used. At each chair, try each distinct value that still has copies left, so two equal values never start separate branches.

from collections import Counter

def permute_unique(nums):
    counts = Counter(nums)
    res, cur = [], []
    def dfs():
        if len(cur) == len(nums):
            res.append(cur[:])
            return
        for x in counts:                 # each distinct value once
            if counts[x] > 0:
                counts[x] -= 1
                cur.append(x)
                dfs()
                cur.pop()
                counts[x] += 1
    dfs()
    return res

permute_unique([1, 1, 2]) returns [[1, 1, 2], [1, 2, 1], [2, 1, 1]]. Time is O(n · number of distinct permutations), space O(n) beyond the output.

A strong answer mentions: counting copies instead of marking positions, looping over distinct values so equal values never branch twice, and restoring the count after the recursive call.

Check what stuck

1. A scheduler must list every possible order in which 5 distinct jobs can run. Which approach fits best?

2. What limits the shown code to roughly O(n² · n!) rather than O(n · n!)?

3. What does the shown permute return for [1, 1, 2]?

Score 60% or more and the lesson is marked complete.