Recursion

Recursion and Backtracking Patterns

Backtracking is one template applied over and over: choose, check, recurse, undo. Subsets, permutations and combinations are the same traversal with different rules about when to record an answer and how far the loop may look. Seeing them as variations rather than three separate algorithms makes the whole topic considerably smaller than it first appears.

2 patterns9 techniquesJava code

Where to start, and what comes next

01
Backtracking
Subsets first, then combinations, then permutations, in that order. Each adds exactly one constraint to the one before it.
Subsets / Power Set Permutations Combinations Constraint Search N-Queens Sudoku Solver
02
Divide & Conquer
Merge sort, quickselect and closest pair. Different shape entirely: split, solve independently, combine.
Merge Sort QuickSelect Closest Pair of Points

If you only have time for three things

The four-step template, and specifically the undo step, which lets one shared path object serve every branch.
The distinction between the three enumeration shapes: subsets record at every node, combinations record at size k, permutations record only at depth n.
Pruning as early as the constraint can be evaluated, because checking only complete candidates is generate-and-test and is exponentially worse.

In an interview

State the complexity before you are asked. Subsets are 2 to the n, permutations are n factorial, and knowing which you are producing shows you understand the shape of your own search. The other thing interviewers watch for is the undo: forgetting it produces answers that are subtly wrong rather than obviously broken, which is much harder to spot in a review.

The idea underneath

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Problems that use these patterns

SubsetsPermutationsCombination SumN-QueensWord SearchGenerate ParenthesesLetter Combinations of Phone Number

Head to head

Recursion vs Iterationa function that calls itself against a loop with explicit state

Questions people ask

Why does the subsets loop recurse with i + 1 rather than start + 1?

It prevents both reuse of an element and duplicate orderings. Passing i + 1 means later calls only look at elements after the one just chosen, so [1, 2] is generated and [2, 1] is not, which is correct because a subset has no order.

How do I handle duplicates in the input?

Sort first, then at each level skip any element equal to its predecessor. That way a repeated value is only chosen once per position, which stops the same subset or permutation being emitted twice.

When do I record the answer?

Subsets record on entry to every call, so every node in the tree is an answer including the empty one. Combinations record only when the path reaches size k. Permutations record only at the leaves, where every element has been used.