Subset sum
Pick numbers from a set that add up to a target. Checking an answer takes a second, finding one takes a search: this problem shows the difference between P and NP.
How to solve it
The subset sum problem: given some numbers and a target, choose a few numbers that add up to it. Checking a proposed answer is easy — add it up. But nobody knows how to find one faster than by searching: $n$ numbers have $2^n$ subsets. It is one of the NP-complete problems, the heroes of the question “P = NP?”.
Step by step
- Sort the numbers in decreasing order: big numbers bring you near the target faster.
- Take numbers in turn while the sum stays within the target. At a dead end, drop the last one taken and try the next (backtracking).
- Prune hopeless branches: if even all the remaining numbers cannot reach the target, stop going down that branch.
- Parity and the last digit help: an odd total needs an odd count of odd numbers.
- Check the answer by adding.
Common mistakes
- Using a number twice — each one may be used at most once.
- Greedily taking the largest numbers and not backing up when the total overshoots.
- Thinking the answer is unique. Several sets may fit, and any of them counts.
- Not checking the sum at the end — an arithmetic slip hurts most right here.