0/1 Subset Sum

01 · Question

Given nonnegative integers values and a nonnegative target, return whether some subset sums to target. Each occurrence may be used once. The empty subset is allowed.

Example: [2,3,7] with target 5 returns true; [2] with target 4 returns false.

02 · Analysis

After each item, reachable[t] records whether the processed prefix has a subset totaling t. Initialize reachable[0]=true. Scan totals downward: reachable[t-value] then comes from the previous item layer, so the current occurrence is not reused. An ascending loop would incorrectly solve the unbounded version and turn [2], target=4 into true. O(nT) time, O(T) space, where T is the numeric target (pseudo-polynomial). The compressed table answers feasibility; reconstructing selected indices needs additional decisions or a fuller table.

03 · Solution

Reference solution

1def has_subset_sum(values, target):
2    reachable = [False] * (target + 1)
3    reachable[0] = True
4    for value in values:
5        for total in range(target, value - 1, -1):
6            reachable[total] |= reachable[total - value]
7    return reachable[target]

Maximum-sum Grid Path

Reconstruct a Longest Common Subsequence