Greedy vs Backtracking: When to Commit and When to Explore
- Greedy choice property is the single deciding test: if the locally optimal pick at each step leads to a globally optimal solution, greedy works; if not, it silently produces wrong answers.
- Backtracking builds solutions incrementally, undoes bad choices with
pop(), and always finds the correct answer at exponential cost (O(2^n) to O(n!)). - Coin change with arbitrary denominations is the canonical greedy failure: taking the largest coin first can poison the remainder, while DP or backtracking finds the true minimum.
- Fractional vs 0/1 knapsack shows how one constraint flips the algorithm from O(n log n) greedy to DP or backtracking.
- Pruning is the main lever for making backtracking practical: reject invalid branches early to avoid exploring millions of dead-end paths.
- In coding interviews, stating the greedy choice property out loud proves you're reasoning about the algorithm, not pattern-matching on problem shape.
One question decides the greedy vs backtracking choice: can you prove that the best local choice is always the best global choice? If yes, greedy. If no, backtracking.
That's it. Everything else is just understanding what that means. And not embarrassing yourself when the interviewer asks "does greedy always work here?"
Both paradigms solve optimization and constraint problems. Both show up constantly in coding interviews. But they work in completely opposite ways. Picking the wrong one doesn't just cost you runtime. It gives you wrong answers. Not "suboptimal" wrong. Just wrong.
One Commits, One Explores
Greedy makes one choice per step and never looks back. It picks the locally best option and moves on. No revisiting. No "what if I'd gone the other way." It's the friend who orders the first thing on the menu, gets a great meal, and never once wonders about the pasta.
Backtracking does the opposite. It makes a tentative choice, recurses forward to see if that choice leads somewhere valid, and if it hits a dead end, undoes that choice and tries the next one. Exhaustive exploration with pruning.
Think of navigating a maze. Greedy is "always turn toward the exit." Backtracking is "try every path, retreat when you hit a wall, keep track of where you've been." Greedy is fast. Backtracking is thorough. The maze doesn't care which one you feel like today.
How Greedy Thinks
Greedy relies on two properties: optimal substructure (the optimal solution contains optimal solutions to subproblems) and the greedy choice property (making the locally optimal choice at each step leads to a globally optimal solution).
The activity selection problem is the clearest example. You have a set of intervals with start and end times. You want the maximum number of non-overlapping activities.
def activity_selection(intervals): intervals.sort(key=lambda x: x[1]) selected = [intervals[0]] for start, end in intervals[1:]: if start >= selected[-1][1]: selected.append((start, end)) return selected
Why does sorting by end time work? Choosing the activity that finishes earliest leaves maximum room for future activities. That's the greedy choice property in action: the locally optimal pick is globally optimal. You prove it with an exchange argument (swap any other choice for this one, and the solution gets no better), and once you have that proof, you're done. O(n log n), no backtracking needed.
How Backtracking Thinks
Backtracking builds solutions incrementally and abandons partial solutions the moment they can't possibly lead to a valid answer.
The canonical example is N-Queens: place N queens on an N×N board so no two share a row, column, or diagonal.
def solve_n_queens(n): solutions = [] board = [] def is_valid(row, col): for r, c in board: if c == col or abs(r - row) == abs(c - col): return False return True def backtrack(row): if row == n: solutions.append(board[:]) return for col in range(n): if is_valid(row, col): board.append((row, col)) backtrack(row + 1) board.pop() backtrack(0) return solutions
board.pop() is the signature move of every backtracking solution. You try a queen placement, recurse, and if that path yields nothing valid, you undo and try the next column. There is no greedy shortcut here. No single column choice is "locally best" in a way that guarantees a global solution. You have to check them all.
Backtracking, before the pruning gets involved.
When Greedy Goes Wrong
The classic trap: coin change with non-standard denominations.
With US coins (1, 5, 10, 25 cents), greedy works. Always grab the largest coin that fits. Minimum count, every time.
Change the coin set to [1, 3, 4] and ask for 6.
Greedy path:
Pick 4 → remaining: 2
Pick 1 → remaining: 1
Pick 1 → remaining: 0
Result: 3 coins
Optimal path:
Pick 3 → remaining: 3
Pick 3 → remaining: 0
Result: 2 coins
The greedy choice (take 4) looked correct at step one but spent the next two steps cleaning up after itself. Greedy saw the 4, grabbed it with confidence, and now there is no path to 2 coins. The greedy choice property doesn't hold for arbitrary coin sets, so greedy gives you the wrong answer. You need dynamic programming or backtracking to find the true minimum.
This is the core failure mode of greedy: it can't recover from a bad early choice. Backtracking can, because every choice is reversible.
Greedy vs Backtracking: What You're Trading
Here's the honest trade-off. There's no middle ground.
| Greedy | Backtracking | |
|---|---|---|
| Time complexity | O(n) to O(n log n) | O(2^n) to O(n!) |
| Space complexity | O(1) to O(n) | O(n) call stack depth |
| Correctness guarantee | Only when greedy choice property holds | Always (given correct logic) |
| Explores all solutions? | No | Yes |
| Can "undo" choices? | No | Yes |
| Typical use case | Optimization with provable greedy structure | Constraint satisfaction, enumeration |
The exponential blowup of backtracking is real. For N-Queens on an 8×8 board, there are 92 valid solutions out of millions of possible configurations to check. Pruning is the main lever for making backtracking practical. The earlier you reject a branch, the less work you do.
Three Problems, One Decision Each
Activity Selection: Greedy wins
Sort by end time, greedily select. The exchange argument proves correctness. O(n log n). No backtracking needed.
Generating All Subsets: Backtracking required
def subsets(nums): result = [] def backtrack(start, current): result.append(current[:]) for i in range(start, len(nums)): current.append(nums[i]) backtrack(i + 1, current) current.pop() backtrack(0, []) return result
There's no greedy shortcut when you need all solutions, not just the best one. Greedy doesn't even apply as a concept here. Complexity: O(n × 2^n). Each element is either in a subset or not.
Fractional Knapsack vs 0/1 Knapsack
This is the cleanest illustration of the divide.
Fractional knapsack: you can take a fraction of any item. Sort by value-per-weight ratio, greedily take the highest-ratio items until full. Greedy works. O(n log n).
0/1 knapsack: take or leave each item whole. Taking the highest-ratio item can prevent you from taking two medium-ratio items that fit together and give more total value. Greedy fails. You need dynamic programming or backtracking.
The only difference between these two problems is "can you take fractions?" One constraint changes the algorithm and the complexity class.
Four Questions Before You Write a Line
Before writing a single line of code, ask these in order:
1. Can you prove the greedy choice property? If the locally best choice at every step leads to a globally optimal solution, verifiable with an exchange argument, use greedy. If you can't sketch the proof, you're probably not in greedy territory.
2. Do you need all solutions, not just one? If the problem asks "generate all" or "find every valid configuration," use backtracking. Greedy can't enumerate.
3. Can an early choice turn out to be wrong? If making choice A now could require you to undo it later because choices interact non-locally, greedy will fail. Use backtracking.
4. Is this a constraint satisfaction problem? Sudoku, N-Queens, graph coloring, combination problems with constraints. These almost always need backtracking. The constraints eliminate branches; you recurse on what's still valid.
One more signal: if you've already checked whether dynamic programming applies and it does, DP is usually faster than backtracking for optimization problems. Memoized recursion beats full enumeration.
What the Interviewer Hears
In a coding interview, the interviewer is watching how you reason about the choice, not just whether you code the right thing.
Jump straight to backtracking and you often get the correct answer but a slow solution. "Can you do better?" is the follow-up. That's your cue to look for a greedy structure.
Claim greedy too fast and you risk a wrong answer and a follow-up counterexample. "Does greedy always work here?" from the interviewer means you haven't justified the choice property. It's a polite way of saying "you guessed."
The right move is to state your reasoning out loud. "I'm considering greedy here. For it to work, picking X locally has to be globally optimal. Let me verify that..." Interviewers don't want to see you guess correctly. They want to see you know why it's correct.
SpaceComplexity runs voice-based mock interviews where you practice exactly this out-loud reasoning, with rubric-based feedback on whether your algorithm justification landed.
Key Takeaways
- Greedy commits to one path and never revisits. Backtracking explores all paths and undoes bad choices.
- Greedy requires a provable greedy choice property. When it holds, you get polynomial time. When it doesn't, you get wrong answers.
- Backtracking is always correct but exponential. Pruning is the main tool to reduce practical runtime.
- Coin change with arbitrary denominations is the textbook case where greedy fails and DP or backtracking is required.
- Fractional vs 0/1 knapsack shows how one constraint changes the paradigm entirely.
- In interviews, justify the greedy choice property explicitly. Silence on this reads as guessing.