Subset Sum
Hard · rating 1600 · dp
The first line contains n and a target t. The second line contains n non-negative integers. Print YES if some subset sums to exactly t, otherwise NO.
Constraints: 1 ≤ n ≤ 40, 0 ≤ t ≤ 104
Editorial
Subset Sum is a canonical dynamic-programming interview problem: decide whether some subset of the numbers adds up to exactly a target.
Approach
Use a boolean DP where dp[t] is true when some subset sums to t. Start with dp[0] = true. For each number, iterate the target downward and set dp[t] = dp[t] or dp[t - num] — downward so each number is used at most once.
dp = [True] + [False]*target
for num in nums:
for t in range(target, num-1, -1):
if dp[t-num]: dp[t] = True
return dp[target]Complexity
Time: O(n × target). Space: O(target). Subset Sum is NP-complete in general; this pseudo-polynomial DP is efficient when the target is bounded.