Subset Sum Equals Target
Given an array of non-negative integers and a target, decide whether some subset sums to exactly the target.
Intuition
This is 0/1 knapsack stripped down to a yes/no question: each number is either in the subset or out, and we only care about reachable sums. Track a boolean row where dp[s] means 'some subset sums to s'. Start with dp[0] = True (the empty subset) and let each number switch on the sums it can now reach. The one detail that matters is the sweep direction: iterating sums downward keeps each number usable at most once, because a cell is only ever read from a lower index it has not yet touched this round.
Approach
Define reachability, not counts
dp[s] = True if some subset of the numbers seen so far sums to exactly s. Only dp[0] starts True — the empty subset always sums to zero.
Apply one number at a time
For num, any sum s that was reachable makes s + num reachable. Written in place: dp[s] |= dp[s - num] for every s >= num.
Sweep downward to keep items unique
Looping s from target down to num means dp[s - num] still refers to the previous row — the state before num existed. An upward sweep would let the same number be reused, which solves a different (unbounded) problem.
Solution & live demo
Edge cases
Immediately True — the empty subset sums to 0, and dp[0] is seeded True.
The inner loop never runs, so dp stays all-False except dp[0] → False.
Harmless: a zero only re-marks sums already reachable, so the answer is unchanged.