A feasibility question
Subset sum asks whether any subset of given non negative integers reaches an exact target. It is the boolean cousin of knapsack: instead of maximizing value, you only track whether a sum is reachable. The state is dp at s, true if some subset sums to s.
The recurrence
Start with dp at zero true, since the empty subset sums to zero. For each number, mark new reachable sums:
- For each existing reachable sum, adding the number reaches a larger sum.
- Process sums from high to low so each number is used at most once.
Partition equal subset sum and counting subsets with a given total are direct extensions, the latter storing counts rather than booleans.
Why high to low
Updating sums in descending order ensures a number is not applied twice within the same pass, mirroring the zero one knapsack constraint.
Key idea
Subset sum reduces the problem to reachability of sums, flipping a boolean table as each number opens new totals, scanned high to low so every number contributes at most once.