Skip to main content

🔙 Backtracking

Backtracking is DFS through a decision tree. Choose, explore, unchoose. If you can describe the problem as "build a solution piece by piece, backtracking when stuck", this is the right tool.

This category contains 16 problems. Use the patterns below to recognize what's being asked, then jump to the problem list at the bottom.

🧠 Key Patterns​

  • Subsets / Power Set — Include or exclude each element.
  • Permutations — Used-set tracking; swap-in-place variant for O(1)O(1) extra space.
  • Combinations / Combination Sum — Start index parameter prevents repeats.
  • Word Search / Path in Grid — Mark cell visited, recurse, unmark.
  • N-Queens / Sudoku — Constraint-satisfaction with placement validation.
  • Partitioning — Palindrome partitioning, IP addresses — try every split point.

⚠️ Common Pitfalls​

  • Forgetting to "unchoose" → results pollute across branches.
  • Copying the current state into results without deep-copying (new List<int>(current)).
  • Missing pruning conditions → TLE on Hard problems.

📚 Study Resources​

📺 Videos​

📖 Books​

🌐 Articles & References​

💻 All Backtracking Problems​

Last updated on