GeeksforGeeks Medium

Subset Sum Equals Target

Given an array of non-negative integers and a target, decide whether some subset sums to exactly the target.

dpknapsackarray

02

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.

How to spot this pattern

0/1 knapsack compressed to one dimension. The row index disappears because each item is processed once, but that only stays correct if the capacity loop runs downward — descending order guarantees dp[s - num] still refers to the previous item's row. Loop direction encoding "use once" versus "use unlimited" is the single most transferable fact in knapsack DP.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

▶1class Solution:
▶2    def isSubsetSum(self, nums, target):
▶3        dp = [False] * (target + 1)
▶4        dp[0] = True
▶5        for num in nums:
▶6            # downward: each num is used at most once
▶7            for s in range(target, num - 1, -1):
▶8                if dp[s - num]:
▶9                    dp[s] = True
▶10        return dp[target]

05

Common pitfalls

Iterating the sum upward

✗ Wrong

for s in range(num, target + 1):
    if dp[s - num]: dp[s] = True

✓ Right

for s in range(target, num - 1, -1):
    if dp[s - num]: dp[s] = True

Ascending order lets a value updated by this item be read again by the same item, so one element gets reused any number of times — that's the unbounded variant. Descending guarantees dp[s - num] is still from the previous round.

Forgetting the empty-subset base case

✗ Wrong

dp = [False] * (target + 1)

✓ Right

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

Sum 0 is always achievable by taking nothing, and that True is the seed every reachable sum chains back to. Without it the whole array stays false.

Stopping the inner loop at zero

✗ Wrong

for s in range(target, -1, -1):

✓ Right

for s in range(target, num - 1, -1):

Below num the expression s - num is negative, which in Python wraps to the end of the list and reads an unrelated entry. Stopping at num keeps every index valid.

06

Edge cases

target = 0

Immediately True — the empty subset sums to 0, and dp[0] is seeded True.

Every number larger than target

The inner loop never runs, so dp stays all-False except dp[0] → False.

Zeros in the array

Harmless: a zero only re-marks sums already reachable, so the answer is unchanged.

07

Complexity

Time

O(n · target)

Space

O(target)

One boolean row replaces the n x target grid; the answer only ever needs the previous row.