templates · Backtracking

Backtracking: permutations

  • "Return all orderings / arrangements"
  • Every element is used exactly once and the order matters
  • Placing items in slots with rules (N-Queens: one queen per row, each column once)

Backtracking: permutations

the one rule

The invariant

used[i] is true exactly when nums[i] is somewhere in path.

write it from memory

The template

all permutations

javajava.util.*
/** Every ordering of nums (values distinct). */static List<List<Integer>> permute(int[] nums) {    List<List<Integer>> out = new ArrayList<>();    build(nums, new boolean[nums.length], new ArrayList<>(), out);    return out;} private static void build(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {    if (path.size() == nums.length) {                 // every slot filled: one answer        out.add(new ArrayList<>(path));               // copy it, path keeps changing        return;    }    for (int i = 0; i < nums.length; i++) {           // any unused element may go next        if (used[i]) continue;                        // already placed        used[i] = true;                               // choose        path.add(nums[i]);        build(nums, used, path, out);                 // explore        path.remove(path.size() - 1);                 // un-choose, in reverse order        used[i] = false;    }}

Unlike subsets, the loop starts at 0 every time: any unused element may come next. used[] stops it from being picked twice.

fill in the blanks — only these lines change per problem

  1. line 9When a path is complete: here, when every element is placed.
  2. line 14Which choices are not allowed right now: used elements, or (with duplicates, after sorting) a value equal to the one just before it while that one is still unused.
  3. line 15Mark the choice, then add it to the path.

the same idea with pruning: N-Queens

javajava.util.*
/** How many ways to place n queens so none attack: a permutation of columns, pruned early. */static int totalNQueens(int n) {    return place(0, n, new boolean[n], new boolean[2 * n], new boolean[2 * n]);} private static int place(int row, int n, boolean[] col, boolean[] diag, boolean[] anti) {    if (row == n) return 1;                           // a queen in every row    int ways = 0;    for (int c = 0; c < n; c++) {        int d = row - c + n, a = row + c;             // which diagonals this square sits on        if (col[c] || diag[d] || anti[a]) continue;   // attacked: prune this branch        col[c] = diag[d] = anti[a] = true;            // choose        ways += place(row + 1, n, col, diag, anti);        col[c] = diag[d] = anti[a] = false;           // un-choose    }    return ways;}

Row by row, a queen goes in a free column. Three boolean arrays answer "is this square attacked?" in O(1).

fill in the blanks — only these lines change per problem

  1. line 11The rule that kills a branch early. Strong pruning is what makes backtracking fast enough.
  2. line 14Undo every mark the choose line set, so the next column starts clean.

complexity

What it costs

time O(n · n!)
There are n! orderings and copying each costs n. Pruning (as in N-Queens) cuts most branches early.
space O(n) extra
used, path and the recursion depth are all at most n, apart from the answer list.

watch out

Common bugs

  • Starting the loop at start like subsets. You get combinations, not permutations.
  • Forgetting used[i] = false when you undo, so elements stay blocked for later branches.
  • The diagonal index row - c can be negative. Add n to keep it a valid array index.

use it

Practise it on

learn it properly