Perfect Sum Problem (Count Subsets)

The Perfect Sum Problem asks you to count — not just find — how many subsets of an array add up to a given target. It is the counting cousin of subset-sum, and it teaches the classic 0/1 knapsack DP grid where every cell is built from the row above it.

The slow way first

The brute-force approach: generate every subset and count the ones that sum to the target. With n elements there are 2^n subsets, so this is O(2^n) — fine for tiny arrays, hopeless once n passes 20 or so.

The question to ask: while I am deciding what to do with one number, what do I wish I already knew? I wish I knew, for every possible running sum s, how many subsets of the numbers I have already considered reach exactly s. If I track that, each new number is a quick update instead of a fresh re-count.

The idea: build a counting grid row by row

Make a grid dp[i][s] = the number of subsets of the first i numbers that sum to exactly s. The base row is "no numbers chosen": there is exactly one subset (the empty one) and it sums to 0, so dp[0][0] = 1 and dp[0][s > 0] = 0.

For each later number a = arr[i-1], every subset either skips it or takes it:

So dp[i][s] = dp[i-1][s] + dp[i-1][s - a] (the take branch only applies when s >= a). The final answer is dp[n][target] — the bottom-right corner of the grid.

Walk through it

Step through the animation. The grid starts with only its base row filled. Each new row folds in one number from arr, and every cell is the sum of two cells directly above: the one straight up (skip) and the one shifted left by a (take). The highlighted cells show the two contributions flowing into dp[i][s]. When the last 3 is folded in, dp[4][6] becomes dp[3][6] + dp[3][3] = 1 + 2 = 3.

Pseudocode

make a grid dp with (n+1) rows and (target+1) columns, all 0
dp[0][0] = 1                          # empty subset sums to 0
for i from 1 to n:                    # fold in arr[i-1]
    a = arr[i-1]
    for s from 0 to target:
        dp[i][s] = dp[i-1][s]         # skip a
        if s >= a:
            dp[i][s] += dp[i-1][s-a]  # take a
return dp[n][target]                  # subsets that hit the target

The Python solution

def count_subsets(arr, target):
    n = len(arr)
    dp = [[0] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for s in range(target + 1):
            dp[i][s] = dp[i - 1][s]
            if s >= arr[i - 1]:
                dp[i][s] += dp[i - 1][s - arr[i - 1]]
    return dp[n][target]

• dp[i][s] counts subsets of the first i numbers that sum to exactly s.
• dp[0][0] = 1 is the base case — the empty subset is the one way to reach a sum of 0.
• The outer loop folds in one number per row; arr[i - 1] is that number (rows are 1-indexed, the array is 0-indexed).
• Line 7 is the skip branch: copy the count from the row above, as if we never use this number.
• Lines 8-9 are the take branch: when the number fits (s >= arr[i - 1]), add the subsets that reached s - arr[i - 1] and then pick this number.
• dp[n][target] is the bottom-right corner — the total count we want.

Complexity

We trade O(n · target) extra space for the grid to turn an exponential search into a pseudo-polynomial fill. (You can shrink the space to O(target) with a single rolling row swept from high to low, but the 2-D grid is easier to see.) The runtime is "pseudo-polynomial" because it depends on the value of target, not just the array length.

When this pattern shows up

Practice