Backtracking, Greedy Reasoning, and Dynamic Programming
Three algorithmic strategies for problems too large to brute-force honestly — when each one applies, and, just as important, when each one gives a wrong answer if misapplied.
What you'll learn
- Implement a backtracking solution that explores and correctly abandons invalid partial solutions
- Explain why a greedy algorithm's local-best choice does not always produce a globally optimal answer
- Implement a memoized (top-down dynamic programming) solution and explain what problem property justifies the approach
Prerequisites
Explanation
Backtracking systematically explores every candidate solution by building one piece at a time, abandoning a partial solution the moment it's provably invalid (rather than continuing to build on top of it) — that early abandonment is the entire point: it's what keeps backtracking from degenerating into a brute-force exploration of every possible full solution. A classic example: placing values one position at a time and, immediately after each placement, checking whether the constraints so far are still satisfiable — if not, "backtrack" (undo the last placement) and try the next candidate value instead, rather than continuing to fill in more positions on top of an already-broken partial solution.
Greedy algorithms make the locally-best choice at each step, never reconsidering it — genuinely simple and fast, but only correct for problems that actually have the "greedy-choice property": making the best immediate choice must be provably compatible with reaching a globally optimal overall solution. Coin-making-change with denominations {1, 5, 10, 25} (always take the largest coin that fits) works correctly with a greedy approach, but the exact same greedy strategy applied to a hypothetical denomination set like {1, 3, 4} for a target of 6 gives a wrong answer: greedy picks 4, then 1, then 1 (three coins), while the actual optimal answer is 3 + 3 (two coins) — the greedy choice property simply doesn't hold for this denomination set. This is precisely why "greedy" is a strategy that requires justifying why it applies to the specific problem at hand, not a default first choice, and a wrong-but-plausible-looking greedy answer is a genuinely common, hard-to-notice class of bug.
Dynamic programming (DP) applies when a problem has overlapping subproblems (the same smaller computation gets needed repeatedly, as naive recursive Fibonacci does — fibonacci(5) calls fibonacci(3) multiple times, redundantly, through different paths) and optimal substructure (an optimal solution to the whole problem is built from optimal solutions to its subproblems). Memoization — caching each subproblem's result the first time it's computed, and returning the cached value on every subsequent request for that exact subproblem, instead of recomputing it — is the direct fix for the overlapping-subproblems case: it turns naive recursive Fibonacci's exponential O(2^n) into a linear O(n), without changing the recursive structure itself at all, just by refusing to redo work already done.
Example
Greedy giving a wrong answer for a denomination set it doesn't actually work for -- and memoized Fibonacci fixing naive recursion's redundant recomputation.
// GREEDY -- correct for {1,5,10,25}, WRONG for {1,3,4}:
function greedyChange(amount, coins) {
const sorted = [...coins].sort((a, b) => b - a);
const used = [];
for (const coin of sorted) {
while (amount >= coin) {
used.push(coin);
amount -= coin;
}
}
return used;
}
console.log(greedyChange(6, [1, 3, 4])); // [4, 1, 1] -- 3 coins, but 2 coins (3+3) is actually optimal!
// MEMOIZED (top-down DP): the SAME recursive structure as naive Fibonacci, but caching results.
function fibMemo(n, cache = new Map()) {
if (n <= 1) return n;
if (cache.has(n)) return cache.get(n); // overlapping subproblem -- reuse, don't recompute
const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
cache.set(n, result);
return result;
}
console.log(fibMemo(40)); // instant -- naive recursion would take a very long time at n=40Try it yourself
Try greedyChange with target 6 and denominations [1,3,4] -- confirm it uses 3 coins, not the optimal 2.
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Guided exercise
Guided exercise
Write climbStairsMemo(n, cache = new Map()) computing the number of distinct ways to climb n stairs, taking 1 or 2 steps at a time (climbStairsMemo(1) = 1, climbStairsMemo(2) = 2, climbStairsMemo(n) = climbStairsMemo(n-1) + climbStairsMemo(n-2)). Use memoization -- this has the exact same overlapping-subproblem shape as Fibonacci.
Checks: base case n=1 · base case n=2 · computes a larger value correctly · runs fast even for a larger n, proving memoization prevents exponential blowup
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Independent exercise
Independent exercise
Write generateSubsets(items) using BACKTRACKING to return every possible subset of items (including the empty set and the full set) as an array of arrays -- build each subset one decision at a time (include or exclude the current item), and 'backtrack' (undo the last inclusion) before trying the next branch. Then write isGreedyChangeSafe(coins) that returns true only for the two SPECIFIC denomination sets [1,5,10,25] and [1,2,5] (return false for any other input, including [1,3,4]) -- modeling that greedy correctness must be verified per denomination set, not assumed.
Checks: generates the correct 4 subsets for a 2-element input · an empty input still yields one subset (the empty set) · a 3-element input yields exactly 2^3 = 8 subsets · correctly identifies a genuinely greedy-safe denomination set · correctly rejects a denomination set where greedy fails
Code editor. Press Escape then Tab to leave the editor if keyboard focus becomes trapped. Press Control+Shift+M inside the editor to toggle Tab-key focus trapping.
Stuck? Get a hint.
Common mistakes
- Assuming a greedy 'take the biggest/closest/cheapest option first' strategy is automatically correct for a new problem, without verifying the greedy-choice property actually holds -- the {1,3,4}-denomination counterexample in this lesson shows how a locally reasonable choice can produce a demonstrably suboptimal final answer.
- Forgetting the 'undo' step in backtracking (e.g. current.pop() after an included branch) -- without it, state built up in one branch incorrectly leaks into sibling branches that should have started fresh.
- Reaching for dynamic programming when subproblems DON'T actually overlap -- memoizing a computation that's never repeated adds bookkeeping overhead for no benefit; DP specifically pays off when the same subproblem is genuinely needed more than once.
Knowledge check
Takeaway
Backtracking prunes invalid partial solutions early instead of exhaustively checking every complete one; greedy algorithms are fast but only correct for problems that genuinely have the greedy-choice property, which must be verified, not assumed; dynamic programming pays off specifically when subproblems overlap and combine via optimal substructure.
Summary
Backtracking builds a solution incrementally, abandoning and undoing invalid partial choices immediately. Greedy algorithms commit to the locally-best choice at each step and are only correct when the greedy-choice property genuinely holds for that specific problem. Dynamic programming (via memoization) caches overlapping subproblems' results to avoid redundant recomputation, turning exponential naive recursion into polynomial time.
References
Your notes
Notes save automatically.
Finished this lesson?
Mark it complete to track your progress and schedule a future review.
AI tutor
The optional AI tutor isn't enabled in this deployment. All lessons, exercises, quizzes, and search work fully without it.