Competitive Programming Academy · Lesson

Subset Sum & Partition

Reach a target with a chosen subset.

The Subset Sum Question

Given numbers and a target, can any subset add up to exactly that target? It is knapsack where value equals weight.

Here you track reachability, not a maximum. Let dp[s] be True when some subset sums to exactly s.

dp = [False] * (target + 1)
dp[0] = True