Count of Subset Sum: Number of Subsets with Given Sum

Key Insights

The count of subset sum problem extends the classic subset sum by counting all valid combinations rather than just checking existence, requiring additive DP transitions instead of boolean OR operations.
Space optimization from O(n × sum) to O(sum) is achieved by processing sums in reverse order, preventing the same element from being counted multiple times in a single subset.
Zeros in the input array require special handling since each zero doubles the count of valid subsets without affecting the sum, a subtle edge case that breaks naive implementations.

Introduction & Problem Statement

Given an array of non-negative integers and a target sum, count the number of subsets whose elements add up to exactly that target. This problem appears constantly in resource allocation, budget planning, and combinatorial analysis.

Consider a practical example: you’re building a shopping cart feature where users have a gift card of exactly $50. You want to show them how many different product combinations they could purchase that total exactly $50. That’s the count of subset sum problem.

Don’t confuse this with the simpler “does a subset exist” variant. That problem returns a boolean—yes or no. Here, we need the exact count. If three different subsets sum to our target, we return 3, not true.

# Example
arr = [1, 2, 3, 3]
target = 6

# Valid subsets: [1, 2, 3], [1, 2, 3], [3, 3]
# Note: The two [1, 2, 3] subsets use different 3s
# Answer: 3

Brute Force Approach: Recursion

The recursive approach mirrors how you’d think about this problem manually. For each element, you have two choices: include it in the current subset or exclude it. This creates a binary decision tree with 2^n leaf nodes.

At each recursive call, you either subtract the current element from your remaining target (include it) or leave the target unchanged (exclude it). When you’ve processed all elements, check if the remaining target is zero—if so, you’ve found a valid subset.

def count_subsets_recursive(arr: list[int], target: int) -> int:
    def helper(index: int, remaining: int) -> int:
        # Base case: processed all elements
        if index == len(arr):
            return 1 if remaining == 0 else 0
        
        # Exclude current element
        exclude = helper(index + 1, remaining)
        
        # Include current element (only if it doesn't exceed remaining)
        include = 0
        if arr[index] <= remaining:
            include = helper(index + 1, remaining - arr[index])
        
        return exclude + include
    
    return helper(0, target)

Time complexity is O(2^n) since we explore every possible subset. Space complexity is O(n) for the recursion stack depth. This works fine for small inputs (n < 20) but becomes unusable beyond that.

Optimizing with Memoization (Top-Down DP)

Look at the recursion tree for arr = [1, 2, 3, 3] with target = 6. You’ll notice the same (index, remaining) pairs appear multiple times. For instance, after processing the first two elements, you might reach (2, 3) through different paths—once by including 1 and excluding 2, once by excluding 1 and including 2.

This overlapping substructure screams dynamic programming. Cache results for each unique (index, remaining) pair.

def count_subsets_memo(arr: list[int], target: int) -> int:
    memo = {}
    
    def helper(index: int, remaining: int) -> int:
        # Check cache first
        if (index, remaining) in memo:
            return memo[(index, remaining)]
        
        # Base case
        if index == len(arr):
            return 1 if remaining == 0 else 0
        
        # Recursive cases
        exclude = helper(index + 1, remaining)
        include = 0
        if arr[index] <= remaining:
            include = helper(index + 1, remaining - arr[index])
        
        # Cache and return
        memo[(index, remaining)] = exclude + include
        return memo[(index, remaining)]
    
    return helper(0, target)

Time complexity drops to O(n × target) since we solve each unique subproblem once. Space complexity is also O(n × target) for the memoization table, plus O(n) for recursion stack.

Bottom-Up Dynamic Programming (Tabulation)

The bottom-up approach eliminates recursion overhead by building the solution iteratively. We construct a 2D table where dp[i][j] represents the count of subsets using the first i elements that sum to exactly j.

The state transition is straightforward:

If we exclude element i-1: inherit count from dp[i-1][j]
If we include element i-1 (and it fits): add count from dp[i-1][j - arr[i-1]]

def count_subsets_tabulation(arr: list[int], target: int) -> int:
    n = len(arr)
    
    # dp[i][j] = count of subsets using first i elements summing to j
    dp = [[0] * (target + 1) for _ in range(n + 1)]
    
    # Base case: one way to make sum 0 (empty subset)
    for i in range(n + 1):
        dp[i][0] = 1
    
    # Fill the table row by row
    for i in range(1, n + 1):
        current_element = arr[i - 1]
        
        for j in range(target + 1):
            # Always can exclude current element
            dp[i][j] = dp[i - 1][j]
            
            # Include current element if it doesn't exceed target sum
            if current_element <= j:
                dp[i][j] += dp[i - 1][j - current_element]
    
    return dp[n][target]

Let’s trace through arr = [1, 2, 3] with target = 3:

Initial (empty subset can make sum 0):
     j=0  j=1  j=2  j=3
i=0   1    0    0    0

After processing arr[0]=1:
i=1   1    1    0    0

After processing arr[1]=2:
i=2   1    1    1    1

After processing arr[2]=3:
i=3   1    1    1    2

Answer: dp[3][3] = 2 (subsets: [1,2] and [3])

Space-Optimized Solution

Notice that each row only depends on the previous row. We can collapse the 2D table into a 1D array. The critical insight: iterate through sums in reverse order to prevent using the same element twice.

If we iterate forward, when computing dp[j], we might use an already-updated dp[j - arr[i]] from the current iteration, effectively including the same element multiple times.

def count_subsets_optimized(arr: list[int], target: int) -> int:
    # dp[j] = count of subsets summing to j
    dp = [0] * (target + 1)
    dp[0] = 1  # Empty subset sums to 0
    
    for num in arr:
        # Iterate in REVERSE to avoid using same element twice
        for j in range(target, num - 1, -1):
            dp[j] += dp[j - num]
    
    return dp[target]

This reduces space complexity to O(target) while maintaining O(n × target) time complexity. For most practical applications, this is the solution you want.

Edge Cases & Variations

Handling Zeros

Zeros are tricky. A zero can be included or excluded from any valid subset without changing the sum. Each zero in the array doubles the count of valid subsets.

def count_subsets_with_zeros(arr: list[int], target: int) -> int:
    # Count and remove zeros
    zero_count = arr.count(0)
    arr_nonzero = [x for x in arr if x != 0]
    
    # Solve for non-zero elements
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for num in arr_nonzero:
        for j in range(target, num - 1, -1):
            dp[j] += dp[j - num]
    
    # Each zero doubles the count (include or exclude)
    return dp[target] * (2 ** zero_count)

Target Sum Zero

When target = 0, the empty subset is always valid. With the standard implementation, dp[0] = 1 handles this correctly. But if zeros exist in the array, you need the zero-handling logic above.

Negative Numbers

The standard DP approach assumes non-negative integers. Negative numbers break the indexing scheme since we can’t have negative array indices. Solutions include:

Offset all values by the minimum negative value
Use a hashmap instead of an array for the DP table
Transform the problem into the “target sum with +/-” variant

Complexity Summary & When to Use

Approach	Time	Space	When to Use
Brute Force	O(2^n)	O(n)	n ≤ 20, quick prototyping
Memoization	O(n × sum)	O(n × sum)	Sparse subproblems, easier to reason about
Tabulation	O(n × sum)	O(n × sum)	Need to trace back actual subsets
Space-Optimized	O(n × sum)	O(sum)	Production code, large inputs

Choose brute force for tiny inputs or when you need to enumerate actual subsets. Use memoization when the problem has sparse valid states. Go with space-optimized tabulation for production systems where you only need the count.