Backtracking

Backtracking tries every choice while building up one partial answer. Define four things: the current state, the choices available, when to stop, and how to undo a choice. Each recursive call is one point in the tree of choices, not necessarily one item of the input.

For subsets, decide at each position whether to include that item. There are 2ⁿ subsets, and copying them all out takes O(n × 2ⁿ) time. For permutations of n distinct values, picking any unused value gives n! results and O(n × n!) work.

What stays true: the current path holds exactly the choices made on the way down to this call, and the "used" state matches it. When a recursive call returns, undo your change, so the next sibling starts from the same state.

Pruning skips branches that can't lead to a valid or better answer. If every value is positive and you're aiming for a sum, going over the target means adding more can't help. With negative values, that pruning would be wrong. When optimizing, if even the best possible finish of a branch can't beat your current answer, skip it.

With duplicate values in the input, two paths can give the same output. To generate unique permutations from a sorted list, skip a value when an equal value right before it hasn't been used on the current path. That picks one order among equal values. Skipping every duplicate would wrongly drop results that use a value twice.

Saving answers (memoization) helps when different branches reach the same state and you only need one answer per state. It helps less when the output must list every path, because then the paths themselves matter. Make sure caching still produces the output the problem asks for.

Practice: LC 78 Subsets, LC 46 Permutations, LC 47 Permutations II, LC 39 Combination Sum, LC 22 Generate Parentheses, LC 79 Word Search, LC 51 N-Queens.

Check your understanding: Which change has to be undone? Is the branch you prune impossible, or just unlikely? Are two paths that reach the same state interchangeable for the output you need?