Backtracking

Permutations

Build every ordering by choosing an unused element at each position.

Medium, about 75 minutes to practise.

1Understand

The idea

Build the ordering position by position: at each step try every element that is not used yet, mark it, recurse, then unmark it. With duplicates in the input, sort first and skip an element that equals the previous one when that previous one is not in use, so each distinct ordering appears once.

Intuition

Build the ordering position by position: at each step try every unused element, mark it, recurse, then unmark. The path length equals n at the leaves.

With duplicates in the input, sort first and skip an element that equals the previous one when that previous one is not used, so each distinct ordering appears once.

Swapping in-place (nums[l] with i) is an equivalent formulation without a separate used array.

What you will be able to do

  • Track used elements
  • Undo every choice

When to use it

  • All orderings / arrangements
  • Letter case or phone-keypad combinations

2See it

Walkthrough

Permutations of [1, 2]

Used-mask (or swap) so each value appears once per path.

1 / 6

i
1
2
01

path []. used=[0,0]. At depth 0 try each unused index.

for i in range(n): if not used[i]

Live template

Line 1 active

1def backtrack(path):
2 if len(path) == len(a): out.append(path[:]); return
3 for x in a:
4 if x in used: continue
5 used.add(x); path.append(x); backtrack(path); path.pop(); used.remove(x)

Complexity: time O(n! · n), space O(n)

Time O(n · n!) to generate all permutations. Space O(n). Duplicate-skipping keeps output size equal to the number of unique perms. Sorting + used-flag skip is the standard fix.

Read the walkthrough as text

Permutations of `[1,2,3]`.

  1. Position 0: try 1, then recurse for positions 1.. with {2,3} left.
  2. Under 1, try 2 then 3 → [1,2,3]; backtrack; try 3 then 2 → [1,3,2].
  3. Similarly branches starting with 2 and 3. Six permutations total.

For [1,1,2], after sorting, when choosing the second 1 while the first 1 is unused, skip, avoids duplicate perms.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • All permutations

    Example. Every ordering of distinct numbers.

    How. Track used indices; choose unused at each depth; copy path at full length.

  • Permutations with duplicates

    Example. Unique permutations when nums has repeats.

    How. Sort; skip same value at same depth if previous equal unused.

  • Phone keypad letter combinations

    Example. Map digits 23 to all letter pairs.

    How. Cartesian backtrack: for each digit, branch over its letters.

  • Generate valid parentheses

    Example. All well-formed strings of n pairs.

    How. Track open and close counts; add ( if open<n; add ) if close<open.

  • Letter case permutations

    Example. All case variants of a string with letters and digits fixed.

    How. Branch flip case on letters; skip on digits; copy at end.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Choice not undone

    Why it happens. Next branch reuses the same path after recursion returns.

    How it fails. Forget path.pop() after recurse, path length grows and used set never clears.

    Fix. Mirror every choose with unchoose: pop path and remove from used after the call.

  • Duplicate permutations

    Why it happens. Swapping equal values produces different index picks that look like different perms.

    How it fails. [1,1,2] emits [1a,1b,2] and [1b,1a,2] as duplicates in output.

    Fix. Sort; at each level skip nums[i]==nums[i-1] when i>start and !used[i-1].

  • Used set by value

    Why it happens. Tracking values in a set is simpler than indices.

    How it fails. Two 1’s: first 1 in used blocks picking second 1, you miss half the perms or over-prune.

    Fix. Track used indices (or visit array by index), not values alone.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons