Dynamic Programming, Backtracking, And Combinatorial Search

What's being tested

These problems test state-space modeling, dynamic programming, and backtracking over constrained combinatorial choices. Interviewers look for whether you can convert messy rules into compact states, prune impossible branches, prove optimal substructure, and implement without exponential blowups where avoidable.

Patterns & templates

• Net-state reduction — collapse inputs into balances, counts, or masks before search; smaller canonical state often changes brute force from impossible to tractable.

• Backtracking with pruning via dfs(i, state) — try valid choices, undo mutations, skip duplicates; worst-case exponential, but acceptable for small n.

• Memoization with @lru_cache or Map<State, Ans> — cache tuple/count-vector/bitmask states; watch mutable arrays as cache keys.

• Bitmask DP for subsets — use dp[mask] or recursive solve(mask); typical complexity O(n * 2^n) or O(3^n) depending transitions.

• Multiset partitioning — represent tiles/items as frequency counts; recursively remove groups, restore counts, and terminate when all counts are zero.

• Minimax / candidate filtering — for feedback-driven guessing, maintain feasible candidates and choose guesses minimizing worst-case remaining set.

• Kadane-style DP on arrays — track best subarray ending here, prefix minima/maxima, or boundary-conditioned states in O(n) time.

Common pitfalls

Pitfall: Starting with raw permutations instead of compressed counts or balances creates factorial search and usually times out.

Pitfall: Forgetting to restore mutated state after a recursive call causes silent corruption across branches.

Pitfall: Caching by non-canonical state, such as unsorted balances, misses equivalent subproblems and destroys memoization effectiveness.

Practice these

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