Suppose we have the following problem, which is simply stated: How can I change a dollar into exactly 26 coins? How might we approach a problem like this? One way is to break it into smaller problems, and try to solve those instead: The number of pennies is going to be a multiple of 5. So your choices are Pennies Other coins ------- ----------- 25 1 20 6 15 11 10 16 5 21 0 25 How does this help? Well, now we've got a set of smaller problems. For example, if there are 25 pennies, we have to figure out how to get 75 cents with 1 coin. That's impossible, so we can forget about it. If there are 20 pennies, we have to get 80 cents with 6 coins. If there are 15 pennies, we need to get 85 cents with 11 coins. And so on: Pennies Other coins Amount remaining ------- ----------- ---------------- 20 6 80 15 11 85 10 16 90 5 21 95 0 26 100 So now we've replaced one large problem with 5 smaller ones: 1. Find 6 coins other than pennies that add up to 80 cents. 2. 11 85 3. 16 90 4. 21 95 5. 26 100 Each of these can be solved by breaking it, in turn, into smaller problems. There are two big advantages to this approach. The first is that if a solution exists, it's sure to be found (if the subproblems are carefully chosen). The second is that, if there are multiple solutions, all of them will be found eventually. |