Here’s a practical decision flowchart you can use during interviews and problem solving:
START
|
v
Can the problem be solved greedily by making
the best local choice at each step?
|
+– YES –> GREEDY ALGORITHM
|
+– NO –>
|
v
Does the problem ask for:
– All possible solutions?
– Any valid solution?
– Enumerating combinations/permutations/subsets?
– Constraint satisfaction?
|
+– YES –>
| |
| v
| Can you prune invalid
| partial solutions early?
| |
| +– YES –> BACKTRACKING
| |
| +– NO –> BRUTE FORCE
|
+– NO –>
|
v
Does the problem have:
1. Optimal substructure?
2. Overlapping subproblems?
|
+– YES –>
| |
| v
| Need optimal value,
| counting, or minimum/
| maximum answer?
| |
| +– YES –> DYNAMIC PROGRAMMING
|
+– NO –>
|
v
Can it be modeled as a graph
(states/nodes + transitions)?
|
+– YES –>
| |
| +– Shortest path –> BFS/Dijkstra
| |
| +– Reachability –> BFS/DFS
| |
| +– DAG ordering –> Topological Sort
|
+– NO –>
|
v
Is it primarily about searching
in a sorted/monotonic space?
|
+– YES –> BINARY SEARCH
|
+– NO –>
|
v
Check specialized techniques:
– Divide & Conquer
– Two Pointers
– Sliding Window
– Heap/Priority Queue
– Union-Find
– Segment Tree
– Trie
– Mathematical/Bit Manipulation
Quick Rule of Thumb
| If you see… | Use |
|---|---|
| Generate all combinations/permutations | Backtracking |
| Optimize (min/max), count ways, repeated states | Dynamic Programming |
| Best local choice always works | Greedy |
| State transitions on nodes | Graph Algorithms |
| Sorted/monotonic answer space | Binary Search |
| Subarray/substring with contiguous window | Sliding Window |
| Split into independent halves | Divide & Conquer |
Backtracking vs Dynamic Programming
Need to explore choices?
|
+– No repeated states –> BACKTRACKING
|
+– Same state reached multiple times –>
DYNAMIC PROGRAMMING
Examples:
- N-Queens → Backtracking
- Sudoku → Backtracking
- Subset Sum (decision) → Backtracking or DP
- Knapsack → DP
- Coin Change → DP
- Longest Common Subsequence → DP
- Generate Parentheses → Backtracking
- Traveling Salesman → DP + Bitmasking (or Backtracking for small inputs)