Count Subsets with Sum K

Medium15–20 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftFlipkart

Given an array of non-negative integers and a target amount k, count how many distinct subsets — distinguished by which positions are chosen, not just which values appear — sum to exactly k. Two equal-valued numbers sitting at different positions in the array count as different elements, so choosing one versus the other produces two separate subsets even though their sums are identical. Just like checking whether any subset reaches a target, every number here faces the same include-or-exclude choice — but now both branches need to be counted, not just checked, since each one might contribute one or more valid ways. The recursion can't stop the instant the running total hits the target, either: a later zero-valued number, for example, can still be freely included or excluded without changing the sum, and each of those is a genuinely different subset. So the tally only happens once every number has been decided on, and the total number of ways is simply the ways found by excluding a number plus the ways found by including it, added together at every step.

Test Case 1:

Input:nums = [3, 4, 4, 7], k = 7

Output:3

Explanation:Three subsets sum to 7: {3,4} (first 4), {3,4} (second 4), and {7} — the two 4s at different positions count as distinct subsets.

Test Case 2:

Input:nums = [2, 2, 2, 2], k = 4

Output:6

Explanation:Choosing any 2 of the four 2s sums to 4 — C(4,2) = 6 ways.

Test Case 3:

Input:nums = [6, 6, 6], k = 12

Output:3

Explanation:Choosing any 2 of the three 6s sums to 12 — C(3,2) = 3 ways.

Constraints

◆1 ≤ nums.length ≤ 20
◆0 ≤ nums[i] ≤ 100
◆0 ≤ k ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Every number is either left out of the subset or included in it, and both choices need to be explored since either could be part of a valid combination. Unlike a yes/no search, the recursion can't stop early the moment the remaining amount hits zero — a later number with value zero, for instance, could still be freely included or excluded without changing the sum, and each of those choices is a distinct subset that must be counted. So the check for a valid subset only happens once every number has been decided on: if the amount still needed is exactly zero at that point, this particular combination of choices counts as one way. Adding up the ways from the "exclude" and "include" branches at every step counts every valid combination exactly once.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] nums;

    public int countSubsetsWithSumK(int[] nums, int k) {
        this.nums = nums;
        return solve(0, k);
    }

    private int solve(int i, int remaining) {
        if (i == nums.length) return remaining == 0 ? 1 : 0;
        if (remaining < 0) return 0;
        return solve(i + 1, remaining) + solve(i + 1, remaining - nums[i]);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every amount from 0 up to k, how many subsets of the numbers seen so far sum to it exactly — a running count array indexed by amount. Amount 0 starts with exactly one way (the empty subset), and each number extends every amount that was already reachable before it by that number's value, adding that many new ways to the amount now reachable through it. Sweeping each number's inner update from k down to the number's own value guarantees the counts being read still reflect the state from before this number was considered, so each number contributes to each subset at most once. After every number has been swept through, the entry at k holds the total count.

TimeO(n × k)

SpaceO(k)