Recursion, Backtracking, And Combinatorics

What's being tested

Recursive decomposition, backtracking search, and combinatorial pruning over permutations, expression generation, nested structures, and constrained selections. Interviewers want to see clean state management, duplicate avoidance, complexity reasoning, and when to switch from exhaustive search to binary search, BFS, or dynamic pruning.

Patterns & templates

• Backtracking template — dfs(path, used) with choose/recurse/unchoose; permutations cost O(n! * n) time and O(n) stack space.

• Duplicate-safe permutations — sort first, then skip nums[i] == nums[i-1] and not used[i-1]; prevents generating equivalent branches.

• Expression insertion DFS — track index, value, last_operand, and expr; multiplication needs undoing previous operand via value - last + last * cur.

• Subset/combination pruning — dfs(start, mask) for character uniqueness; use bitmasks for O(1) overlap checks and early reject invalid strings.

• Nested recursion — compute depthSum(node, depth) by accumulating integers and recursing into lists; stack depth equals maximum nesting depth.

• Constraint search alternative — shipping capacity is binary search on answer using canShip(capacity) in O(n log(sum(weights))), not backtracking.

• Grid distance fallback — shortest path in an unweighted grid is BFS, O(mn) time; recursion risks stack overflow and wrong shortest-path ordering.

Common pitfalls

• Pitfall: Using a set of full permutations to remove duplicates works but wastes memory; sort-and-skip is the expected interview solution.

• Pitfall: Forgetting multiplication precedence in expression generation gives plausible but incorrect results; carry last_operand explicitly.

• Pitfall: Describing exponential complexity vaguely is weak; state output-sensitive bounds like O(n! * n) or O(4^n) where applicable.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.