Each item is used at most once; state = (index, remaining capacity), decide include vs. exclude at each step. Recognize "0/1 knapsack in disguise": subset-sum, partition, and target-sum problems are all this pattern wearing a different costume.
Sub-patterns
- A — Classic Knapsack. Maximize value under a capacity constraint.
- B — Subset Sum. Can a subset hit an exact target sum?
- C — Partition Equal Subset Sum. Split into two equal-sum halves.
- D — Target Sum. Assign +/- signs to hit a target.
Practice set (5)
- Medium — Partition Equal Subset Sum, Target Sum, Ones and Zeroes, Last Stone Weight II
- Hard — Profitable Schemes
Pending
Classic Knapsack
Maximize value under a capacity constraint, each item used at most once.
Pending
Subset Sum
Determine whether some subset of the input hits an exact target sum.
Pending
Partition Equal Subset Sum
Split the input into two subsets with equal sums.
Pending
Target Sum
Assign a + or - sign to each number to hit an exact target.
Notes from readers
Comments — via GitHub