Backtracking vs Dynamic Programming
Combinatorial Path Reporting vs Subproblem State Collapse
When you must explore every winding path to print combinations, versus when a few numbers summarize your state for dynamic programming.
"Does the problem ask you to return or print ALL valid combinations and paths, or does it ask for a COUNT, MAXIMUM, MINIMUM, or BOOLEAN EXISTENCE?"
Ask this single question during the first two minutes of reading the problem prompt. The answer decides your fundamental pattern.
Imagine Old Delhi around Chandni Chowk with its labyrinth of winding bazaars. A visiting food blogger asks you: 'Take me through every single route from Sis Ganj Gurdwara to Paranthe Wali Gali, and write down every turn so I can publish the whole list.' You have to walk every alley, note every corner, and backtrack when you hit a dead end (Backtracking: you must output every physical path). Now imagine a quick-commerce delivery manager asks: 'What is the quickest travel time to reach Paranthe Wali Gali, or how many distinct routes avoid the roadwork?' The manager does not need you to recite 200 route transcripts; they only need the optimal number for each junction (DP: subproblems collapse to a single number per intersection).
When to Choose Which Pattern
Backtracking (Exhaustive Search with Pruning)
Option A- ✓The problem return type is a collection of sequences: e.g. List<List<Integer>> or List<String>.
- ✓You must build actual combinatorial objects: subsets, permutations, board states (N-Queens), or grid word paths.
- ✓The state required to make future decisions is the entire accumulated sequence of past decisions.
- ✓No polynomial state representation exists because every distinct path must be returned.
Dynamic Programming (Memoization and Tabulation)
Option B- ✓The problem asks for an aggregate scalar: min cost, max profit, number of ways, or boolean possibility.
- ✓Future decisions depend only on a small state summary (such as current index i and remaining budget w), not on how you reached that state.
- ✓Subproblems overlap repeatedly.
- ✓The search space collapses from exponential to polynomial.
Side-by-Side Worked Examples
Compare concrete implementations side by side to see how the code structure diverges.
Word Search(LC 79)
LeetCode ↗Explore the grid cell by cell. At each character match, mark the cell visited, recurse in 4 directions for word[k + 1], and backtrack by restoring the original character when returning. Because you must avoid reusing cells within the same path, state is path-dependent.
def exist(board: list[list[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def backtrack(r: int, c: int, k: int) -> bool:
if k == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[k]:
return False
temp = board[r][c]
board[r][c] = '#'
found = (backtrack(r+1, c, k+1) or backtrack(r-1, c, k+1) or
backtrack(r, c+1, k+1) or backtrack(r, c-1, k+1))
board[r][c] = temp
return found
return any(backtrack(r, c, 0) for r in range(rows) for c in range(cols))Word Break(LC 139)
LeetCode ↗Let dp[i] be true if prefix s[0...i] can be segmented using dictionary words. To check dp[i], check if there is some j < i such that dp[j] is true and s[j...i] is in the dictionary. You do not need to record the segmented sentences, only whether each prefix is breakable.
def wordBreak(s: str, wordDict: list[str]) -> bool:
words = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]The Decision Matrix
Output Format
Full collection of combinations, paths, or permutations
Single scalar value (boolean, count, min, max)
State Dependency
Path-dependent (requires past choice history)
Markovian (future depends only on current state variables)
Complexity Order
O(2^N), O(K^N), or O(N!) (exponential output)
O(N * K) or O(N^2) (polynomial runtime)
Memoization Viability
Rarely viable if output itself is exponential in size
Core requirement (stores overlapping subproblem results)
| Evaluation Factor | Backtracking (Exhaustive Search with Pruning) | Dynamic Programming (Memoization and Tabulation) |
|---|---|---|
| Output Format | Full collection of combinations, paths, or permutations | Single scalar value (boolean, count, min, max) |
| State Dependency | Path-dependent (requires past choice history) | Markovian (future depends only on current state variables) |
| Complexity Order | O(2^N), O(K^N), or O(N!) (exponential output) | O(N * K) or O(N^2) (polynomial runtime) |
| Memoization Viability | Rarely viable if output itself is exponential in size | Core requirement (stores overlapping subproblem results) |
Where Candidates Go Wrong (Top Traps)
Attempting DP to return all permutations or paths
Missing the undo step in Backtracking
Using Backtracking without memoization for counting or boolean queries
Related Walkthroughs in our DSA Course
Explore step-by-step solutions with 4-language code flaps (Java, C#, TS, Python) and visual memory dry runs.
Word Search (Grid Backtracking and State Reversal)
Generate Parentheses (Combinatorial Pruning)
Partition Equal Subset Sum (0/1 Knapsack DP)
Decode Ways (Counting Ways with 1D DP)
"Backtracking generates full combinatorial structures at the cost of exponential runtime. Dynamic Programming delivers polynomial execution time, but only works when decisions can be summarized into compact numerical states."
Practice Real Indian Hiring Loops
See the exact problems asked at Flipkart, Swiggy, Razorpay, PhonePe, and Amazon with verified candidate reports and round structures.