LESSON 18 · PATTERN GUIDE

Backtracking Basics

Build candidate solutions step by step and undo each choice when exploring another branch.

FIRST, LEARN THE PATTERNBacktracking is depth-first search over choices. A path represents a partial solution; reaching a valid stopping condition records a result.

The task asks for all subsets, permutations, combinations, or ways to reach a target.

How to approach it

Choose, recurse, then undo. Define what choices are available next and when the path is complete.

Watch out for

The number of outputs can be exponential; avoid unnecessary copying and duplicate paths when duplicates exist.

A CLOSER EXPLANATION

The search tree branches once for each available choice. A recursive call represents one partial decision path; once the path is complete, record it. Undoing the last choice restores the state so the next branch starts from the same prefix.

NOW YOU TRY

Practice question

List all subsets of [a, b].

EXAMPLEitems = [a, b]Give your answer before revealing the explanation.

Show a hint

For each item, explore one branch that skips it and one branch that includes it.

Show an answer

[], [a], [b], [a, b]

CONNECT IT TO REAL LIFE

Backtracking Basics at work

A café offers three optional toppings. How many different topping combinations can a customer choose, including no toppings?

Show one possible approach

8 combinations, because each of the 3 toppings has two choices: include or skip. Backtracking explores those binary choices and records each completed selection.

Practice next

Use these problem IDs to find additional practice for this pattern:

464777789039