Build a solution one choice at a time, and undo each choice before trying the next, to explore every possibility.

Earn the full sheet below.

When to reach for it

• 'Combination/subset' wording is the tell.
• Need every arrangement, not just one answer.
• Word Search: incremental validation counts 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. Base case: index ran off the list.
3. Decision Tree. The choice is the problem: take the element, recurse, untake it.
4. Result List Initialization. An empty list, handed 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 on InterviewCrunch and the sheet is yours. Free accounts included. Members can download every sheet right away.

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

Every pattern has a sheet. See the full set.