☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Count subsets with sum K

Hard TUF ID 318 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n non-negative integers and a target k. Count the subsets whose elements add up to exactly k. Subsets are told apart by indices, not values: in [1, 2, 2] the subsets {arr[0], arr[1]} and {arr[0], arr[2]} are different even though both are {1, 2}. The count can be huge, so return it modulo 10^9 + 7.

Typical constraints: 1 ≤ n ≤ 100, 0 ≤ arr[i] ≤ 1000, 0 ≤ k ≤ 1000. Note that zeros are allowed; that single detail is where most solutions to this problem go wrong.

Example 1

arr = [1, 2, 2, 3], k = 3
answer = 3          // {1, first 2}, {1, second 2}, {3}

Example 2

arr = [0, 0, 1], k = 1
answer = 4          // {1}, {0a, 1}, {0b, 1}, {0a, 0b, 1}: each zero may or may not join

From “is there one” to “how many”

The existence version of this problem asks can(i, t) = can(i - 1, t) OR can(i - 1, t - arr[i]). Counting changes only the combining operator. Every subset of the first i elements either excludes the last of them or includes it, never both, so the two groups are disjoint and their counts simply add:

ways(i, t) = ways(i - 1, t) + ways(i - 1, t - arr[i - 1])     (second term only if arr[i - 1] ≤ t)

This “replace OR by +” step works for any pick / not-pick recursion whose branches produce disjoint sets of outcomes, which is the case whenever the branches differ in a decision about the same element.

The zero trap and the base case

In the existence version, a common base case is “if t == 0, return true”, because the empty subset always works. Copying that into the counting version as “if t == 0, return 1” is wrong when zeros exist. It says there is exactly one way to finish (take nothing more), but each remaining zero can be taken or not, giving 2^(zeros left) ways. On [0, 0, 1] with k = 1 the early exit returns 1 instead of 4.

The fix used throughout the Java file is to index by prefix length and stop only when no elements remain:

ways(0, t) = 1 if t == 0, else 0         // with no elements, only the empty subset exists
answer     = ways(n, k)

Zeros are then just ordinary elements: for t unchanged, ways(i, t) = ways(i - 1, t) + ways(i - 1, t - 0), which doubles the count, exactly as it should. (Striver’s version keeps the index-based base case at i == 0 and returns 2 when arr[0] == 0 and t == 0; that is the same fix written differently.)

Approach 1: Recursion

Intuition. count(i, t) is the number of subsets of arr[0..i-1] with sum t. Decide about the last available element arr[i - 1]: skip it, or take it if it fits. Add the two counts, reducing modulo 10^9 + 7.

Algorithm.

  1. If i == 0, return 1 when t == 0, else 0.
  2. notTake = count(i - 1, t).
  3. take = count(i - 1, t - arr[i - 1]) if arr[i - 1] ≤ t, else 0.
  4. Return (notTake + take) % MOD.
static int recursive(int[] arr, int k) {
    return count(arr.length, k, arr);
}

static int count(int i, int t, int[] arr) {
    if (i == 0) return t == 0 ? 1 : 0;              // no elements left: only the empty subset, with sum 0
    int notTake = count(i - 1, t, arr);
    int take = arr[i - 1] <= t ? count(i - 1, t - arr[i - 1], arr) : 0;
    return (notTake + take) % MOD;
}

Complexity. Time O(2^n): the recursion visits every subset. Space O(n) for the stack.

The sum of two values below MOD is at most 2,000,000,012, which still fits in an int (the limit is 2,147,483,647), so int arithmetic with one % per addition is safe.

Approach 2: Memoization

Intuition. The state is (i, t) with 0 ≤ i ≤ n and 0 ≤ t ≤ k. Many different choices among the later elements leave the same (i, t), and the count from there is the same each time. Caching gives one computation per state.

0 is a legitimate count, so the table is filled with -1 to mean “not computed”.

Algorithm.

  1. Allocate dp[n + 1][k + 1] filled with -1.
  2. Same recursion; return dp[i][t] when known, store it otherwise.
static int memoization(int[] arr, int k) {
    int[][] dp = new int[arr.length + 1][k + 1];
    for (int[] row : dp) Arrays.fill(row, -1);      // counts are >= 0, so -1 = unknown
    return memo(arr.length, k, arr, dp);
}

static int memo(int i, int t, int[] arr, int[][] dp) {
    if (i == 0) return t == 0 ? 1 : 0;
    if (dp[i][t] != -1) return dp[i][t];
    int notTake = memo(i - 1, t, arr, dp);
    int take = arr[i - 1] <= t ? memo(i - 1, t - arr[i - 1], arr, dp) : 0;
    return dp[i][t] = (notTake + take) % MOD;
}

Complexity. Time O(n · k). Space O(n · k) plus O(n) stack.

Approach 3: Tabulation

Intuition. dp[i][t] depends only on row i - 1, so fill rows 1..n in order starting from dp[0][0] = 1 and the rest of row 0 equal to 0. The inner loop must start at t = 0, not t = 1: a zero element adds new subsets with sum 0, so column 0 changes from row to row.

Algorithm.

  1. dp[0][0] = 1.
  2. For i = 1..n and t = 0..k: dp[i][t] = dp[i - 1][t] + (arr[i - 1] ≤ t ? dp[i - 1][t - arr[i - 1]] : 0), modulo MOD.
  3. Return dp[n][k].
static int tabulation(int[] arr, int k) {
    int n = arr.length;
    int[][] dp = new int[n + 1][k + 1];
    dp[0][0] = 1;                                   // the empty prefix has exactly one subset: {}
    for (int i = 1; i <= n; i++) {
        for (int t = 0; t <= k; t++) {              // t starts at 0: zeros add subsets with sum 0
            int notTake = dp[i - 1][t];
            int take = arr[i - 1] <= t ? dp[i - 1][t - arr[i - 1]] : 0;
            dp[i][t] = (notTake + take) % MOD;
        }
    }
    return dp[n][k];
}

Dry run on Example 1 (arr = [1, 2, 2, 3], k = 3):

i (element) t = 0 1 2 3
0 (none) 1 0 0 0
1 (1) 1 1 0 0
2 (2) 1 1 1 1
3 (2) 1 1 2 2
4 (3) 1 1 2 3

In row 3, t = 2 becomes 2 because there are now two different 2s; t = 3 becomes 2 because each of them pairs with the 1. Row 4 adds {3} itself, giving the answer 3.

Complexity. Time O(n · k), space O(n · k).

Approach 4: Space optimized

Intuition. One array ways holds the current row. For each element x, update ways[t] += ways[t - x] with t going from k down to x. Because t - x < t, the value read has not yet been updated for x, so it still counts subsets without x; each element is therefore used at most once.

Zeros work automatically: with x = 0 the loop runs t from k down to 0 and does ways[t] += ways[t], doubling every entry, which is precisely the effect of an optional zero.

Algorithm.

  1. ways[0] = 1, the rest 0.
  2. For each x in arr, for t from k down to x: ways[t] = (ways[t] + ways[t - x]) % MOD.
  3. Return ways[k].
static int spaceOptimized(int[] arr, int k) {
    int[] ways = new int[k + 1];
    ways[0] = 1;
    for (int x : arr) {
        for (int t = k; t >= x; t--) {              // right to left: ways[t - x] still excludes x
            ways[t] = (ways[t] + ways[t - x]) % MOD;
        }
    }
    return ways[k];
}

Complexity. Time O(n · k), space O(k).

Edge cases and pitfalls