Count of Subset Sum

Counting subsets that sum to a target works by building, for every prefix of the array and every achievable partial sum, the number of ways to reach that sum — each new element either joins existing subsets (carrying their count forward into a larger sum) or is skipped, so the count at dp[sum] accumulates contributions from both choices instead of just a yes/no reachability flag.

Recognize the pattern

• Phrase is "number of subsets/ways" (not "does a subset exist") that hit an exact sum or partition target.
• Elements are used at most once each (0/1, not unbounded) and are positive.
• Answer scales combinatorially — duplicates in the input produce distinct subsets by position, e.g. {1,3} and {1,3} from two different 1's both count.
• Sibling problems that reduce to this same table: Equal Subset-Sum Partition (target = totalSum/2, only possible if totalSum is even); Minimum Subset-Sum Difference (scan reachable sums near totalSum/2); Target Sum, assigning +/- to each element to hit a value target — split elements into a positive set P and negative set N, then sum(P) - sum(N) = target and sum(P) + sum(N) = totalSum, so sum(P) = (totalSum + target) / 2; feed that derived value in as S and count subsets exactly as below (no solution if totalSum + target is odd or negative).

Brute force → optimal

Brute force: recurse on each index with a choice to include or exclude it, summing the count of ways from both branches; base case succeeds when the running sum hits 0. This explores every subset: O(2ⁿ) time, O(n) recursion stack.

Optimal: the recursion only depends on (index, remainingSum), and remainingSum ranges over just 0..S — a classic overlapping-subproblems + optimal-substructure signature, so memoize or tabulate into a 2-D (or rolled 1-D) DP: O(n·S) time, O(S) space.

Complexity from first principles

Let dp[s] = number of ways to form sum s using elements processed so far. Recurrence per new element num:

dp_new[s] = dp_old[s]                 // exclude num
          + dp_old[s - num]  (if s >= num)   // include num

There are n elements, each requiring a pass over S+1 sum slots → exactly n·(S+1) constant-time updates: Time O(n·S). Only the previous row is ever read, so one array of length S+1 suffices, iterated right-to-left per element to avoid reusing an item twice in the same pass: Space O(S) (O(n·S) if you keep the full 2-D table for traceability/teaching).

Worked example

Input {1, 1, 2, 3}, S = 4. Rows = elements processed so far, columns = sum 0..4, dp[0]=1 always (empty subset makes sum 0). Each cell reads only the previous row's values (right-to-left pass), which is what keeps this 0/1 rather than unbounded.

Trace the last two rows by hand: before processing 2, dp = [1,2,1,0,0]. Reading old values right-to-left, dp[4] += dp[2]=1 (→1), dp[3] += dp[1]=2 (→2), dp[2] += dp[0]=1 (→2), giving [1,2,2,2,1]. Then processing 3: dp[4] += dp[1]=2 (→1+2=3), dp[3] += dp[0]=1 (→2+1=3), giving the final row [1,2,2,3,3]. dp[4] = 3 matches direct enumeration: {1,1,2}, {1,3} using the first 1, and {1,3} using the second 1 — three position-distinct subsets, exactly what the recurrence counts.

Reference implementation (Java)

static int countSubsetSum(int[] nums, int S) {
    int[] dp = new int[S + 1];
    dp[0] = 1; // empty subset makes sum 0
    for (int num : nums) {
        for (int s = S; s >= num; s--) {
            dp[s] += dp[s - num];
        }
    }
    return dp[S];
}

Pitfalls

• Iterating the sum loop left-to-right reuses the same element multiple times in one pass, silently turning this into unbounded knapsack (Coin Change-style) instead of 0/1 counting.
• Forgetting dp[0] = 1 makes every count come out zero — the empty subset is the base case that seeds all others.
• Confusing this with reachability (boolean DP for "can we hit sum S") — that variant uses OR, this uses +, and mixing them gives a yes/no answer instead of a count.
• Overflow: counts grow combinatorially (up to 2ⁿ); use long for large n.
• Zeros in the input double the count of every sum they touch: a 0 can be independently included or excluded without changing any sum, so each zero multiplies the answer by 2 (the update dp[s] += dp[s-0] degenerates to dp[s] += dp[s]). This is correct behavior, but a common surprise if you expect zeros to be inert.

When to use / when not

Use when items are used at most once, the target is small enough that S fits in memory (pseudo-polynomial, not polynomial in the numeric value of S), and you need a count rather than existence or an optimal value. If S is astronomically large but n is small (≤ ~20), prefer meet-in-the-middle: split into two halves, enumerate all 2^n/2 subset sums per half, sort one half and binary-search/count matches against S - sum from the other — O(2^n/2·log(2^n/2)) time, no dependency on S at all. If you only need existence (not count), the boolean 0/1 knapsack reachability DP is cheaper to reason about and equally O(n·S).

Takeaways

• Counting DP replaces boolean OR with integer addition — same state space, richer answer.
• dp[0] = 1 is the seed; every other count is built from it.
• Iterate sums right-to-left per element to preserve the 0/1 (use-once) constraint.
• Target Sum reduces to this table via S = (totalSum + target) / 2; when S is huge but n is small, switch strategies entirely to meet-in-the-middle.

Recall: why must the inner sum loop run from S down to num, not from num up to S?

Pattern generalizes Kadane-adjacent 0/1 knapsack counting; canonical treatment in Grokking the Coding Interview (Subset Sum pattern) and CLRS-style DP-over-subset-sums exercises.