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 it or skip it. Step through the walk below.

Walkthrough

Take / skip tree for [1, 2, 3]

+1+2+3skipskip+3skipskip+2+3skipskip+3skip[]112123121131[]2232[]3[]
Step 1 of 9
path = []

Start at the root with an empty path. Each level decides one number: the left child takes it, the right child skips it.

current path
leaf reached: a subset

A node shows the path so far (12 means [1, 2]).

  • 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) → [""].