Sonith ManakkatEarlier parts showed individual algorithms. This part steps back to three styles of designing one, each with a different attitude to making choices. Greedy commits to whatever looks best right now. Divide and conquer splits the problem into smaller copies. Backtracking tries a choice, and if it leads nowhere, undoes it and tries another. Knowing which style fits a problem is half of solving it. Each section has a plain picture and an Expert view.
Three styles at a glance
- GreedyAlways grab the nearest tasty thing on the table
- Divide and conquerSplit a big job among helpers, then combine their work
- BacktrackingIn a maze, try a path, back up at a dead end, try another
Expert viewA note on how they relate
Dynamic programming (part 6) can be seen as a fourth style that sits between these: like divide and conquer it splits problems, but it stores overlapping answers. Backtracking is a systematic search of a tree of choices, closely related to depth-first search from part 5. Many problems can be attacked with more than one style, and the styles differ in what they guarantee: greedy gives a guarantee only when a special property holds, while backtracking can be made to find an answer or prove none exists, at a possibly large cost.
- 1Is a local best choice provably safe?Yes Greedy: fast and simpleNo keep going
- 2Do small pieces repeat and combine into the answer?Yes Dynamic programming: store and reuse answersNo keep going
- 3Can the problem split into independent pieces?Yes Divide and conquer: solve the pieces, then combineNo keep going
- 4OtherwiseBacktracking: try choices, undo dead ends and prune early
Takeaway. Check for a safe greedy rule first, and fall back to search only when nothing cheaper fits.
Greedy: take the best choice now
- List the choicesWhat can I pick next?
- Pick the best-lookingBy some fixed rule
- Never undo itNo second thoughts
- RepeatUntil the job is done
Greedy is fast and simple, but it is only correct when local best choices add up to a global best. That depends on the problem.
Works
- Standard coin sets: biggest coin first gives the fewest coins
- Activity selection: always take the activity that finishes earliest
Fails
- Coins 1, 3 and 4 for amount 6
- Greedy: 4 + 1 + 1 is three coins, but 3 + 3 is two
Expert viewWhen can you trust greedy?
Two properties are usually proved: the greedy-choice property (some optimal solution begins with the greedy choice) and optimal substructure (after that choice, the rest is a smaller problem of the same type). The standard method is an exchange argument: take any optimal solution and show you can swap in the greedy choice without making it worse. Well-known correct greedy algorithms include activity selection by earliest finish, Huffman coding, and Dijkstra's algorithm for non-negative weights (part 5). Without such a proof, assume greedy may fail and test it on small cases against a slower exhaustive method.
Divide and conquer: split the job
Show the 9 steps as text
- Start: split the row in halves again and again until single bars.
- Merge positions 1 to 2: two sorted halves become one sorted run.
- Merge positions 3 to 4: two sorted halves become one sorted run.
- Merge positions 1 to 4: two sorted halves become one sorted run.
- Merge positions 5 to 6: two sorted halves become one sorted run.
- Merge positions 7 to 8: two sorted halves become one sorted run.
- Merge positions 5 to 8: two sorted halves become one sorted run.
- Merge positions 1 to 8: two sorted halves become one sorted run.
- Sorted: the last merge joined the two big halves.
Binary search (part 4) is another example, with a twist: it splits the sorted list in half, throws one half away, and continues on the other.
Expert viewThe recurrence, in words
The cost of such an algorithm is described by a recurrence. Merge sort sorts two halves, each half the size, and then does work proportional to n to merge. In words: the time for n items equals twice the time for n over 2 items, plus about n. That solves to O(n log n), because there are about log n levels of halving and each level does about n work in total. Binary search does one half-sized piece plus a constant amount of work: the time for n equals the time for n over 2, plus a constant, which solves to O(log n). The master theorem is a general rule that solves many recurrences of this shape. Divide and conquer fits best when the pieces are independent, which also makes them easy to run in parallel. If pieces overlap heavily, dynamic programming is usually the better tool.
Backtracking: try, undo, try again
- ChoosePick an option for the next step
- ExploreCarry on from there
- Dead end?Stop and undo the last choice
- Try the next optionUntil a solution is found or options run out
- Choose to Explore Pick an option for the next step and carry on from there
- Explore to Dead end The next step has no allowed option, so this path is stuck
- Dead end to Choose Undo the last choice and go back to choosing
- Explore to Solution Every step has a valid option: a solution
Takeaway. Undoing a failed choice and trying the next option is the whole trick.
The classic example is the N-queens puzzle: place N chess queens on an N by N board so that none attacks another (no two share a row, column or diagonal). Take the 4 by 4 board and place one queen per row, going down.
A dead end
- Row 1 column 1, row 2 column 3, then row 3 has no safe square
- Back up and try column 4 in row 2; that fails too, so row 1 must move
A solution
- Row 1 column 2, row 2 column 4, row 3 column 1, row 4 column 3
- No queen attacks another
Backtracking just tries every possibility
Pruning skips whole groups of choices as soon as they cannot work
Expert viewPruning and cost
Backtracking explores a tree of partial solutions, and pruning cuts a branch as soon as a constraint is broken. In the worst case the search can still be exponential, because pruning only helps as much as the constraints let it; the 4 by 4 board has just two solutions, but the search effort grows very quickly with N. Good practice is to check constraints as early as possible, choose the most constrained variable next (the idea behind many sudoku solvers), and keep fast data structures for "is this square attacked?" checks. Sudoku is the same pattern: fill a cell with a digit not already in its row, column or box; if a later cell has no legal digit, back up. Backtracking suits constraint puzzles, generating combinations and permutations, and finding any or all solutions.
Choosing between them
| Style | Idea | Good when | Watch out for |
|---|---|---|---|
| Greedy | Take the best-looking choice, never undo | A proven greedy property holds | Can be wrong without a proof |
| Divide and conquer | Split, solve pieces, combine | Pieces are independent and combining is cheap | Overlapping pieces repeat work |
| Dynamic programming | Split, store overlapping answers | Overlapping subproblems and optimal substructure | Table memory |
| Backtracking | Try, undo, try again | Constraint puzzles and "find all solutions" | Possible exponential time |
Try it by hand
- Draw a 4 by 4 gridUse paper and coins for queens
- Row 1Put a queen in column 1
- Row 2Find a safe column; mark squares a queen attacks
- Hit a dead endIf a row has no safe square, lift the last queen
- Move it onTry the next column in that row, and carry on
- Count solutionsTry every start; there are two solutions
Greedy never looks back, divide and conquer shares the load, backtracking is allowed to say "oops".
Frequently asked questions
How do I know whether greedy works?
You need an argument or proof for the problem. A good habit is to compare greedy with an exhaustive method on small cases and look for a counter-example.
Is backtracking just brute force?
It is a smarter search: it abandons partial solutions early. In the worst case it can still be very slow.
Is merge sort the only divide and conquer algorithm?
No. Binary search, quick sort and fast Fourier transforms are other well-known examples.
Can I mix these styles?
Yes. Many practical solutions combine them, for example backtracking with greedy ordering of choices to find solutions sooner.