Count Subsets with Sum K

count the subset that can give sum k

Count Subsets with Sum K

Problem Statement

You are given an array, arr, of positive integers, and a positive integer, K.

Select any collection of positions from the array (each position can be used at most once), and count how many such selections have a total sum equal to K.

Equal values at different positions are treated as separate choices.

Return the count, modulo 10⁹ + 7.

Examples

Example 1

Input: arr = [2, 3, 5, 16, 8, 10], K = 10

Output: 3

Explanation: The valid subsets are [2, 3, 5], [2, 8], and [10].

Example 2

Input: arr = [2, 2, 2, 2], K = 4

Output: 6

Explanation: Any pair of positions adds up to 4. With four positions, there are 6 different pairs possible.

Recursion: The Core Idea

Every position in the array offers two choices: skip the current value, or pick it.

• Skipping leaves the remaining target sum unchanged.
• Picking subtracts the current value from the remaining target sum.

By adding the counts from both choices, we cover every possible subset, without any overlap or double-counting.

We define a state, solve(index, remaining), representing the number of subsets we can form using elements from positions 0 through index, that add up to exactly remaining. The very first call uses (N - 1, K), since at the start, the entire array and the full target sum are both available.

Algorithm

• Start with solve(N - 1, K), since the whole array needs to be considered to reach the target K.
• Return 1 whenever remaining == 0, since this means the current selection has already formed one valid subset.
• At index == 0, simply compare arr[0] with remaining, since only the first element is left to consider.
• Explore the skip branch, using (index - 1, remaining), since excluding the current value doesn't change the required sum.
• Explore the pick branch only when arr[index] <= remaining, since positive values can't be picked if they're larger than what's left to reach.
• Add the results of the skip and pick branches together, since they represent two completely separate (non-overlapping) sets of choices.
• Apply the modulo 10⁹ + 7 at every merge step, to keep the running count within the required range.

Memoization (Top-Down)

We follow the recursive logic above, storing each (index, remaining) pair's result in a dp grid, so we never recompute the same subproblem twice.

perfectSum(arr, K) {
    let n = arr.length;

    let dp = Array.from({ length: n }, () => Array(K + 1));

    function recurr(index, remaining, dp) {
        if (remaining === 0) {
            return 1;
        }

        if (index === 0) {
            return arr[0] === remaining ? 1 : 0;
        }

        if (dp[index][remaining] !== undefined) {
            return dp[index][remaining];
        }

        let pick = 0;

        if (arr[index] <= remaining)
            pick = recurr(index - 1, remaining - arr[index], dp);

        let notPick = recurr(index - 1, remaining, dp);

        return dp[index][remaining] = (pick + notPick) % 1000000007;
    }

    return recurr(n - 1, K, dp);
}

Tabulation (Bottom-Up)

We build the answer forward, starting from the first element, instead of recursing backward from the last one.

• For every row, dp[i][0] = 1, since there's always exactly one way to reach a sum of 0 — by picking nothing.
• For the very first element (dp[0][arr[0]]), we directly set it to 1, representing the one way to reach that sum using just the first element.
• For every other element and every possible sum from 1 to K, we calculate the pick option (if the current value fits within the remaining sum) and the skip option (just carrying forward the previous row's value), and add them together, applying the modulo as we go.

perfectSum(arr, K) {
    let n = arr.length;

    let dp = Array.from({ length: n }, () => Array(K + 1).fill(0));

    for (let i = 0; i < arr.length; i++) {
        dp[i][0] = 1;
    }

    dp[0][arr[0]] = 1;

    for (let i = 1; i < n; i++) {
        for (let sum = 1; sum <= K; sum++) {
            let pick = 0;
            if (arr[i] <= sum) pick = dp[i - 1][sum - arr[i]];

            let notPick = dp[i - 1][sum];

            dp[i][sum] = (pick + notPick) % 1000000007;
        }
    }

    return dp[n - 1][K];
}