Backtracking Example: Choosing Dishes That Fit a Budget Exactly

Pruning by a running total is the idea this example shows: when the choices have costs and the solution has a limit, a branch can stop as soon as its total passes the limit, and sorting the costs first lets one failure rule out every larger cost at once. The surface is a lunch order, where the reader must see the budget as a rule to prune by.

A group has exactly 17 pounds of vouchers that must be spent in full, on dishes priced 11, 4, 9, 6 and 7, each ordered at most once. Which sets of dishes cost exactly 17?

The search sorts the prices to 4 6 7 9 11 and builds each set in increasing order of price, so each node chooses the next dish from the prices after the last one taken. It keeps a running total. If the total reaches 17, it records the set. If adding the next price would pass 17, it stops the loop: every later price is larger, so it would pass 17 too. A run printed the tree it walked, with the pruned branches noted.

Under 4 6, the search records 4 6 7 at 17, then tries 9, which would make 19, and stops the loop there; 4 6 11 is never considered. Under 7, the branch 7 9 is kept at 16, but adding 11 would make 27, and no price below 11 remains. The run found two sets, 4 + 6 + 7 and 6 + 11.

The search kept 14 partial sets, where taking or skipping each of 5 dishes would build all 32 subsets and check each one's total at the end. The saving grows quickly with the number of dishes, because every pruned node takes its whole subtree with it.

What this shares with Pruning a Branch as Soon as It Breaks a Rule is the test made on the partial solution, the moment a choice could break the rule. There the rule was an attack between queens; here it is a running total against a budget. Sorting the prices is what this surface adds: in sorted order, one total over the budget proves every later choice at that node fails, so one test prunes several branches.