Micro-Drill #183 — Backtracking vs DP: when to use which

BACKTRACKING vs DP — DECISION GUIDE
────────────────────────────────────
USE BACKTRACKING when:
  □ Need ALL solutions (not just count/optimal)
  □ Solution is a sequence of choices (permutation, path)
  □ Constraints are complex (placement rules, validity)
  □ Search space can be pruned effectively
  Examples: N-Queens, Sudoku, all permutations

USE DP when:
  □ Need COUNT or OPTIMAL VALUE (not all solutions)
  □ Overlapping subproblems exist
  □ Optimal substructure holds
  □ State space is polynomial
  Examples: coin change, LCS, knapsack

BOTH work but pick wisely:
  "Number of ways to..." → usually DP (count)
  "Find all ways to..."  → usually backtracking (enumerate)
  "Min cost to..."       → usually DP (optimize)

HYBRID: precompute with DP, enumerate with backtracking
  Example: palindrome partitioning (DP palindrome check
           + backtracking to list all partitions)