Subset Sum, in depth: existence and counting tables, bitsets, every target in one pass, size-k counts, undoing an item and the pseudo-polynomial wall

The problem family, precisely

Fix n non-negative integers, nums, and a target T. A subset is a choice of indices, so equal values at different positions give different subsets: in [2, 2] two subsets sum to 2. Five questions recur, and each wants a slightly different method.

1. Existence. Does any subset sum to T?
2. Count. How many do? The answer can reach 2ⁿ, so it usually comes with a modulus.
3. All targets. For every s from 0 to T, is s reachable, and how many ways? Partition problems need this.
4. Fixed size. How many subsets of exactly k elements sum to T?
5. Dynamic. Items arrive and leave, with a query after each change.

The reference for all of them is the brute force below. It is obviously right, and a property test against it catches nearly every indexing mistake in faster code.

from itertools import combinations

def count_brute(nums, target):
    """Reference: try every subset by index. O(2^n * n); use only for n <= 20."""
    total = 0
    for r in range(len(nums) + 1):
        for combo in combinations(range(len(nums)), r):
            if sum(nums[i] for i in combo) == target:
                total += 1
    return total

Building the table from first principles

Process items one at a time. Let reach_i(s) say whether some subset of the first i items sums to s. Before any item only the empty subset exists, so reach₀(0) is true and all else false. When item x arrives, every subset either leaves x out (old sum) or takes it (sum plus x), so reach_i(s) = reach_i-1(s) OR reach_i-1(s - x) for s at least x.

Counting uses the same split with addition, because the two cases are disjoint: count_i(s) = count_i-1(s) + count_i-1(s - x), with count₀(0) = 1. That 1 is the empty subset; forgetting it leaves every entry at zero.

One array suffices if s runs from T down to x: dp[s - x] has not been updated yet in this pass, so it still holds the value from before x. Running upwards reads an entry that already includes x, reusing the item and turning the problem into the unbounded coin-change count.

def can_reach(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True                      # the empty subset reaches 0
    for x in nums:
        for s in range(target, x - 1, -1):   # descending: each item once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

def count_ways(nums, target, mod=None):
    dp = [0] * (target + 1)
    dp[0] = 1
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] += dp[s - x]
            if mod:
                dp[s] %= mod
    return dp                          # dp[s] = number of subsets with sum s

Both cost O(nT) time and O(T) memory. count_ways returns the whole array on purpose; see the all-targets section below.

Worked example

Take nums = [3, 1, 4, 2, 2] and T = 6. The counting array over sums 0 to 6 evolves like this, one row per item processed:

The final entry, 4, matches a hand count: {4, 2a}, {4, 2b}, {3, 1, 2a} and {3, 1, 2b}. The last row answers more than was asked: three subsets sum to 3 ({3}, {1, 2a}, {1, 2b}) and every sum from 0 to 6 is reachable. The two equal 2s double some counts; if the problem wants distinct value sets rather than index sets, group equal values and choose how many copies of each to use.

The bitset: the same table, sixty-four sums at a time

For existence, each entry is one bit and the update is the same for every s: the new row is the old row OR the old row shifted up by x. Packing the row into machine words turns T updates into about T/64 word operations. In C++ that is std::bitset<N> b; b |= b << x;; in Python the built-in integer is an arbitrarily long bit vector whose shift and OR run in C.

def reachable_bitset(nums, target):
    """Bit s of `bits` is 1 when some subset sums to s. Python ints are arbitrary
    precision, so one shift-or processes the whole row a machine word at a time."""
    mask = (1 << (target + 1)) - 1
    bits = 1                           # only sum 0 is reachable at the start
    for x in nums:
        bits = (bits | (bits << x)) & mask
    return bits

bits = reachable_bitset([3, 1, 4, 2, 2], 12)
print([s for s in range(13) if bits >> s & 1])   # every reachable sum

The mask caps the integer at T + 1 bits; without it the number grows to the sum of all items. There is no loop direction to get wrong, because the shift reads the old value in one go. In Python the speed-up is large because the inner loop leaves the interpreter, but measure it on your own data. When the reachable set is sparse, compressed structures such as Roaring bitmaps apply the same idea.

Counting without overflow, and every target in one pass

Counts grow fast: 60 zeros give 2⁶⁰ subsets summing to 0. Python integers just grow and slow down; Java, C++ and Go wrap silently. The usual contract is a count modulo a prime such as 10⁹+7, applied inside the loop as count_ways does. Each zero doubles every count (z zeros multiply by 2^z); the table handles that as long as the loop includes s = x. If you filter zeros out, multiply back at the end.

Because the table holds every sum from 0 to T, one pass answers any number of target queries in O(1) each. Equal partition is dp[S/2] for total S; the smallest split difference is S - 2s for the largest reachable s at or below S/2. If you are running the DP once per query, build the row once instead.

Counting subsets of exactly k items

A size constraint adds a dimension: dp[j][s] counts subsets of j items summing to s, and item x moves subsets from (j - 1, s - x) to (j, s). Iterate j downwards so the row you read still predates x.

def count_size_k(nums, k, target):
    # dp[j][s] = subsets of exactly j items with sum s
    dp = [[0] * (target + 1) for _ in range(k + 1)]
    dp[0][0] = 1
    for x in nums:
        for j in range(k, 0, -1):              # descending in j as well as s
            row, prev = dp[j], dp[j - 1]
            for s in range(target, x - 1, -1):
                row[s] += prev[s - x]
    return dp[k][target]

Cost is O(nkT) time and O(kT) memory. For feasibility only, make each row a bitset and update with row |= prev << x.

Removing an item without rebuilding

Counting tables can be run backwards. Adding x replaced dp[s] with dp[s] + dp[s - x] from high s to low. To undo it, subtract from low to high: when the loop reaches s, dp[s - x] has already been restored, so dp[s] - dp[s - x] is exactly the old dp[s].

def add_item(dp, x):
    for s in range(len(dp) - 1, x - 1, -1):
        dp[s] += dp[s - x]

def remove_item(dp, x):
    # Exact inverse of add_item. Ascending order: when we reach s, dp[s - x]
    # has already been restored to its value before x was added.
    if x == 0:                  # adding a zero doubled every entry
        for s in range(len(dp)):
            dp[s] //= 2         # modulo p: multiply by the inverse of 2
        return
    for s in range(x, len(dp)):
        dp[s] -= dp[s - x]

dp = [1] + [0] * 10
for x in [3, 1, 4, 2]:
    add_item(dp, x)
remove_item(dp, 4)          # now dp counts subsets of [3, 1, 2]
assert dp[:7] == [1, 1, 1, 2, 1, 1, 1]

That gives O(T) updates for a pool of items that changes between queries, and a cheap leave-one-out: remove each item, answer "how many subsets avoid it?", add it back, for O(nT) total instead of O(n²T).

It does not work for the boolean or bitset table: OR forgets how many ways reached a sum, so you cannot tell whether a sum depended on the removed item. For dynamic reachability, keep counts modulo a large prime and treat nonzero as reachable. A true count that is a multiple of the prime shows as zero; with a random 61-bit prime that is unlikely, and two primes make it negligible.

Negative numbers, reconstruction and huge targets

Negative values. Shift every sum by the magnitude of the negative total, N, so index s + N stands for sum s, and size the array to cover the full range. A negative item reads a higher index, so its loop must run ascending (in bitset form, shift right by |x|); a descending loop would reuse it.

Getting a subset back. Keep one bitset row per item (nT/8 bytes) and walk back from T: if the sum was reachable before item i, skip it, otherwise take it and subtract its value. Target Sum shows the walk.

When T is the problem. O(nT) is not polynomial: T takes only about log₂T bits to write down, so the time is exponential in input size. That is why subset sum is NP-complete yet easy for small numbers; the running time is called pseudo-polynomial. With n = 40 and values near 10¹² no table fits, but meet in the middle (enumerate 2²⁰ sums per half, sort one, match the other) finishes in seconds. First divide all values and T by their greatest common divisor and drop items larger than T. See Big-O notation for how bounds are stated and read.

Choosing the method by constraint

When both n and the values are large, no exact method here applies; use backtracking with pruning, an integer programming solver or an approximation scheme.

Testing it

Nearly every bug here is an off-by-one in a loop bound or direction. A random comparison against brute force finds them in seconds; include zeros, duplicates, an empty list and T = 0.

import random

for trial in range(2000):
    nums = [random.randint(0, 9) for _ in range(random.randint(0, 10))]
    t = random.randint(0, 30)
    assert count_ways(nums, t)[t] == count_brute(nums, t)
    assert can_reach(nums, t) == (count_brute(nums, t) > 0)
    assert (reachable_bitset(nums, t) >> t & 1) == (count_brute(nums, t) > 0)
    dp = count_ways(nums, 30)              # remove a random item, compare with a rebuild
    if nums:
        remove_item(dp, nums.pop(random.randrange(len(nums))))
        assert dp == count_ways(nums, 30)

Failure modes

• Ascending loop when adding. Items are reused and you get the coin-change count.
• Forgetting dp[0] = 1. Every count is zero; the empty list with T = 0 must return 1.
• Loop stops at x + 1. The single-item subset {x} is missed and zeros are ignored.
• Overflow in fixed-width languages. Plausible, wrong results; take the modulus inside the loop.
• Removing from a boolean table. There is no inverse; use counts.
• Allocating T + 1 entries when T is 10¹⁰. Check the bound first.

What to do next

1. Write count_brute and the random test first, then the version you need.
2. Decide which of the five questions you are answering, and check whether one table serves all your queries.
3. Use the Python integer bitset or std::bitset for any existence question; it is shorter and faster.
4. Apply the modulus inside the loop, and test with zeros and duplicates.
5. If items change over time, keep a counting table and use the ascending remove.
6. Check n and T against the choice table before coding, and read dynamic programming fundamentals if the recurrence still feels like a trick rather than a split into two cases.