Build a solution one choice at a time, then undo it to try the next. That walk explores every possibility.

Earn the full sheet below.

When to use it

• 'Combination/subset' wording is the tell.
• You need every arrangement, not just one answer.
• Validation problems like Word Search count too.

What's on the sheet

Combinatorial problems all follow these steps; step 3 is what changes. Validation ones like Word Search return True or False instead of collecting results.

1. Recursive Helper Function. Four arguments ride along on every call: index, path, input, result.
2. Valid Result Check. Recursion stops once the index runs off the list.
3. Decision Tree. The choice is the whole problem. Take it, recurse, then untake it.
4. Result List Initialization. An empty result list goes to the helper.

Watch out

• Append curr.copy(), not curr. Skip the copy and every future backtrack mutates the same list already sitting in res.
• Every recursive call passes along the same things: the index, the path so far, the input, and the result. Drop one and the recursion loses its place.
• Asked for a count instead of the combinations themselves? Return len(res), not res.

How to earn it

Solve half of the Backtracking problems and the sheet is yours. A free account works fine, and everyone earns their sheets the same way.

Want to see a finished sheet first? Preview the Two Pointers sample.

Every pattern has a sheet. See the full set.