Thinking in Decision Trees

Backtracking, lesson 1 of 3

Thinking in Decision Trees

See every 'generate all ...' problem as a walk through a tree of choices.

10 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

            Some problems don't ask for *one* answer, they ask for

all of them: every subset, every ordering, every way to place 8 queens, every word you can spell on a keypad.

            **Backtracking** builds each candidate one decision at
            a time. After exploring a decision it *undoes* it and
            tries the next one, like walking a maze and stepping
            back at every dead end.

The picture: a decision tree. To list the subsets of [1, 2, 3], make one yes/no decision per number:

                []
     take 1 /        \\ skip 1
         [1]          []
   +2 /    \\       /    \\
   [1,2]   [1]    [2]    []
   / \\     / \\    / \\    / \\
[123][12][13][1][23][2] [3] []
  • Each level is one decision.
  • Each root-to-leaf path is one candidate.
  • 3 yes/no decisions → 2 × 2 × 2 = 8 leaves = 8 subsets.

Backtracking is just a depth-first walk of this tree. It keeps one path in memory (the current partial answer), never the whole tree.

Example

Walk the take/skip tree

The indentation is the depth in the tree. Notice path.pop(): after the "take" branch finishes, we remove the number so the "skip" branch starts from the same state. That undo step is the backtrack.

Quiz

How many times is explore called (internal nodes and leaves)?

Why it's exponential (and why that's fine). The work is at least the number of answers:

Problem Answers n = 10 n = 20
subsets 2ⁿ 1,024 ~1 million
permutations n! ~3.6 million ~2.4 × 10¹⁸
k-combinations C(n, k) C(10,5) = 252 C(20,10) = 184,756

Copying each answer costs up to O(n), so subsets is O(n · 2ⁿ) and permutations O(n · n!). No clever trick beats that when you must output every answer, so interviewers keep n tiny.

Example

Brute force with itertools vs growth

itertools is great in real code, but it only covers the plain cases. The moment a rule appears ("sum must equal target", "no two queens attack") you need your own search, so you can prune: stop exploring a branch that can't work.

Quiz

A problem says 1 ≤ n ≤ 20 and asks you to return every subset of the input. What is the worst-case number of subsets?

Exercise

All binary strings

Write binary_strings(n) that returns a list of every string of length n made of "0" and "1", in increasing order ("0" before "1" at every position).

Use backtracking: a shared path list, append a digit, recurse, then pop it. When the path has length n, record "".join(path).

binary_strings(2) → ["00", "01", "10", "11"] and binary_strings(0) → [""].