Count of Subset Sum (Count How Many Subsets Reach an Exact Target)

• Count of Subset Sum is the counting variant of the 0/1 Knapsack pattern.
• Instead of a boolean reachability array, we keep an integer count array dp[t] holding how many subsets sum to exactly t.
• The base case is dp[0] = 1 because the empty subset is the one subset that sums to zero.
• For each number, we sweep targets from S down to the number and accumulate: dp[t] += dp[t - num].
• Time is **O(N * S) and space is O(S)** where N is the element count and S is the target.

What is the Count of Subset Sum problem?

The Count of Subset Sum problem asks: given a set of positive numbers and a target S, how many distinct subsets sum to exactly S? This is the counting variant of the subset-sum feasibility problem. Where the feasibility version asks "is it possible?", this version asks "how many ways?"

For example, given {1, 2, 3, 4} and target 5, the answer is 3: subsets {1, 4}, {2, 3}, and {1, 2, 2} do not apply here because 2 appears once, so the valid subsets are {1, 4}, {2, 3}, and {5} if 5 were present. With {1, 1, 2, 3} and target 4, the subsets are {1, 3} (first 1), {1, 3} (second 1), and {1, 1, 2}, giving a count of 3.

How does the counting DP array work?

We use an integer array dp of size S + 1. The entry dp[t] holds the number of subsets that sum to exactly t.

• Base case: dp[0] = 1 because there is exactly one subset that sums to zero: the empty subset.
• Transition: for each number num, sweep from S down to num and add: dp[t] += dp[t - num].
• Answer: dp[S] after processing all numbers.

The logic is that every subset previously summing to t - num becomes a new subset summing to t once we include the current number, so those counts carry forward.

package com.bank.service;

public class SubsetSumCountService {

    /**
     * Counts how many subsets of the given charges sum to exactly the target.
     * Used by National Bank of India fraud team to analyze disputed amounts.
     */
    public static long countSubsets(int[] charges, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1; // One subset (empty) sums to zero

        for (int charge : charges) {
            for (int t = target; t >= charge; t--) {
                dp[t] += dp[t - charge];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] charges = {500, 1000, 1500, 2000, 500};
        int disputedAmount = 2500;
        long ways = countSubsets(charges, disputedAmount);
        System.out.println("Number of charge combinations totaling "
            + disputedAmount + ": " + ways);
    }
}

javac -d out com/bank/service/SubsetSumCountService.java
java -cp out com.bank.service.SubsetSumCountService

Number of charge combinations totaling 2500: 3

Why does dp[0] = 1 matter so much?

The base case dp[0] = 1 seeds the entire computation. Without it, no target would ever accumulate a count because every count propagates from this initial value. The one represents the empty subset, which is a valid subset in combinatorics. Interviewers often test this understanding by asking what happens if you set dp[0] = 0 instead: the answer is that dp[S] would be zero for every target, making the algorithm useless.

// WRONG: dp[0] = 0 means no counts ever propagate
long[] dp = new long[target + 1];
// dp[0] defaults to 0 -> dp[target] will always be 0

// CORRECT: dp[0] = 1 seeds the counting
long[] dp = new long[target + 1];
dp[0] = 1;

How is this different from the boolean subset-sum?

The only structural differences between counting and feasibility are the array type and the update operation.

| Aspect | Subset Sum (Feasibility) | Count of Subset Sum |
|---|---|---|
| DP array type | boolean[] | long[] |
| Base case | dp[0] = true | dp[0] = 1 |
| Update | dp[t] = dp[t] \|\| dp[t - num] | dp[t] += dp[t - num] |
| Result | true or false | integer count |
| Overflow risk | None | Possible with large inputs |

The sweep direction (high to low) and the 0/1 constraint are identical. Recognizing that the counting variant is just the feasibility variant with OR replaced by addition is the key insight.

What are the edge cases?

Several edge cases require careful handling.

• Target is zero: the answer is always 1 (the empty subset), regardless of the input numbers.
• All elements larger than target: no element fits, so the answer is 0.
• Zeros in the input: each zero doubles the count because it can be included or excluded without changing the sum. If there are z zeros, multiply the result by 2^z. The standard algorithm handles this naturally because dp[t] += dp[t - 0] doubles dp[t].
• Duplicate elements: handled naturally because each element is processed independently.

package com.bank.core;

public class SubsetCountEdgeCases {
    public static void main(String[] args) {
        // Target zero: always 1 (empty subset)
        System.out.println(countSubsets(new int[]{100, 200}, 0)); // 1

        // Zeros in input: each zero doubles the count
        System.out.println(countSubsets(new int[]{0, 0, 500}, 500)); // 4

        // All elements too large
        System.out.println(countSubsets(new int[]{5000, 6000}, 100)); // 0
    }

    static long countSubsets(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int t = target; t >= num; t--) {
                dp[t] += dp[t - num];
            }
        }
        return dp[target];
    }
}

1
4
0

What is the time and space complexity?

The time complexity is **O(N * S) where N is the number of elements and S is the target. For each element, we iterate over at most S targets. The space complexity is O(S)** for the one-dimensional count array.

Like the partition problem, this is pseudo-polynomial. For very large targets, the DP array can become impractically large, and you may need to discuss alternative approaches such as meet-in-the-middle for smaller N.

Why use long instead of int for counts?

Counts can grow exponentially with the number of elements. For an array of N elements, the maximum number of subsets is 2^N. With N = 60, that exceeds the range of int (about 2.1 billion). Using long provides safety up to about 9.2 * 10^18.

// With 30 elements, counts can reach up to 2^30 = ~1 billion
// int overflows silently; long stays safe
long[] dp = new long[target + 1]; // Always use long for counts

What should a senior engineer know?

A senior engineer should understand several deeper aspects.

• Modular arithmetic: many competitive programming variants ask for the count modulo 10^9 + 7. In that case, take the modulo at each addition step to prevent overflow.
• Reconstruction: to list all subsets (not just count them), use a two-dimensional DP table and backtrack, but be aware the output can be exponential in size.
• Zeros handling: zeros in the input are a common interview trap. Each zero independently doubles the subset count because it can be included or excluded without affecting the sum.
• Relationship to coin change: if each number can be used unlimited times (low-to-high sweep), the problem becomes the coin change counting problem.

package com.bank.service;

public class SubsetCountModular {
    private static final long MOD = 1_000_000_007L;

    public static long countSubsetsMod(int[] nums, int target) {
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int t = target; t >= num; t--) {
                dp[t] = (dp[t] + dp[t - num]) % MOD;
            }
        }
        return dp[target];
    }
}

What are common interview follow-up questions?

Interviewers often extend this problem in several directions.

• Target Sum problem (LeetCode 494): assign + or - to each element to reach a target. This reduces to counting subsets that sum to (total + target) / 2.
• Partition into two subsets with minimum difference: requires running the DP for all possible targets up to total / 2 and finding the largest reachable target.
• Count with exactly K elements: add a second dimension tracking how many elements are chosen.