Backtracking

The general idea

Backtracking builds a solution step by step. At each step you choose one option, check the rules, and go deeper. If the rules fail, or you reach a dead end, you go back (undo) the last choice and try another one.

All the tries make a tree: the top is the empty answer, each level is one more choice. Backtracking walks this tree depth first. A cut branch saves a lot of work. The method uses recursion: each level is one call.

solve(k):            // fill slot k
  for each option v:
    if v is allowed at slot k:
      x[k] = v
      if k is the last slot: print x
      else solve(k + 1)
    // loop continues = go back and try next v

Cartesian product

The Cartesian product of sets A and B is every pair (a, b). Backtracking: slot 1 takes each value of A; for each, slot 2 takes each value of B. Every option is allowed, so nothing is cut.

For A = {1, 2} and B = {x, y, z} we get 2 × 3 = 6 pairs: (1,x) (1,y) (1,z) (2,x) (2,y) (2,z).

Permutations

A permutation of n items uses all n items once, in every order. Rule: a value is allowed only if it is not already used. That is the rule that cuts the red branches in the 3D.

There are n! permutations: 3 items give 3! = 6 (123, 132, 213, 231, 312, 321), 4 items give 24.

Arrangements

An arrangement of n items taken k at a time is an ordered list of k different items. Same code as permutations, but the answer is complete after k slots, not n.

Count: A(n, k) = n! / (n − k)!. For n = 5, k = 2: 5 × 4 = 20.

Combinations

A combination of n items taken k at a time is a group of k items where order does not matter. To avoid repeats, force the values to increase: x[k] must be bigger than x[k − 1]. That cuts all repeated orders.

Count: C(n, k) = n! / (k! (n − k)!). For n = 4, k = 2: (1,2) (1,3) (1,4) (2,3) (2,4) (3,4), which is 6.

Subsets

A subset picks any items of a set, possibly none. Backtracking: for each item decide "take" or "leave". That is 2 choices per item, so a set of n items has 2ⁿ subsets. For {a, b, c} there are 8.

Try it

Take three coloured pencils and list all the orders on paper. Do it by backtracking: fix the first pencil, list the rest, then go back and change the first. In the 3D, before pressing Next step, guess whether the next move is a place, a rejection, or a step back.

Key formulas and definitions

• Permutations of n items: n!
• Arrangements: A(n, k) = n! / (n − k)!
• Combinations: C(n, k) = n! / (k! (n − k)!)
• Subsets of n items: 2ⁿ
• Cartesian product of sets with sizes p and q: p × q pairs

Worked examples

Common mistakes

• Forgetting to undo the choice when going back, so the old digit stays in the slot.
• Not checking the rule before going deeper, which makes the tree huge.
• Mixing up arrangements (order matters) and combinations (order does not matter).
• Missing the base case: print the answer only when all slots are filled.