Classic Backtracking Problems

This unit dives into the most important backtracking problems you'll encounter in interviews. These problems fall into two main categories: selection problems (choosing elements to include) and constraint problems (satisfying complex rules while building solutions).

Selection problems like subsets, combinations, and permutations form the foundation of backtracking. Once you master these patterns—understanding when to use i+1 vs i in recursion, how to handle duplicates, and how to track used elements—you can solve dozens of related problems. Constraint problems like word search, N-Queens, and Sudoku add complexity by requiring you to check validity conditions and manage state more carefully.

What You'll Learn

• Combinations and Subsets: The most common backtracking problems including subsets, combinations, combination sum, permutations, and problems like generating parentheses and phone number letter combinations. You'll learn the key patterns: when to allow reuse, how to skip duplicates, and how to track used elements.

• Backtracking with Constraints: More complex problems involving grids and constraint satisfaction, including word search in 2D boards, N-Queens placement, Sudoku solving, palindrome partitioning, IP address restoration, and maze navigation. These problems require managing multiple constraints simultaneously.

Key Concepts

For selection problems, the critical decisions are: (1) Can elements be reused? (2) Does order matter? (3) Are there duplicates to handle? For constraint problems, focus on efficient validity checking, state management, and early pruning. Both categories use the same choose-explore-unchoose template, just with different state management strategies.