Does the selected variant allow zero values?

No. The selected TakeUForward variant uses positive array values. A zero-inclusive variant needs adjusted base cases because picking or skipping zero creates separate subsets with the same sum.

Can negative values use the same DP table?

No. Columns from 0 through K cannot represent negative intermediate sums. Negative values require an offset table or a map keyed by reachable sums.

Is modulo needed after every addition?

Yes. Modular addition preserves the final remainder and prevents intermediate counts from growing beyond standard integer limits.

Is a subset required to be contiguous?

No. A subset may use any array positions, while every position appears at most once and selection order has no effect.

Count Subsets with Sum K Using Dynamic Programming

Q: Do equal values create separate subset choices?

Yes. Array positions define choices, so arr = [2, 2, 2, 2] and K = 4 produce 6 position pairs.

An array arr containing positive integers and a positive integer K are given. Select any collection of array positions, with every position used at most once, and count the selections having total sum K.

Equal values at different positions remain separate choices. Return the count modulo 10⁹ + 7.

Example 1

Input: arr = [2, 3, 5, 16, 8, 10], K = 10
Output: 3
Explanation: 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 forms sum 4, and four positions contain 6 different pairs.

Practice it by yourself before moving onto the solutionTry now

Recursion

Every array position offers two choices: skip the current value or pick it. Skipping keeps the remaining sum unchanged, while picking subtracts the current value from the remaining sum. Adding the counts from both choices considers every possible subset without overlap.

The state solve(index, remaining) represents the number of subsets that can be formed using elements from positions 0 through index with the required sum remaining. The initial call uses (N - 1, K) because the complete array and target are available at the beginning.

Algorithm

Start with solve(N - 1, K) because the complete array must be considered for forming the target K.
Return 1 when remaining == 0 because the current selection has formed one valid subset.
At index == 0, compare arr[0] with remaining because only the first element remains available.
Explore the skip branch with (index - 1, remaining) because excluding the current value leaves the required sum unchanged.
Explore the pick branch only when arr[index] <= remaining because positive values cannot be picked if they exceed the remaining sum.
Add the skip and pick counts because the two branches represent disjoint choices of whether to include the current element.
Apply modulo 10⁹ + 7 during every merge to keep the count within the required modular range.

Dry Run

1 / 2

Diagram 1

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5private:
6    int modulo = 1000000007;
7
8    // Counts valid subsets inside one array prefix.
9    int solve(
10        int index,
11        int remaining,
12        vector<int>& arr
13    ) {
14        // A zero remainder forms one completed subset.
15        if (remaining == 0) {
16            return 1;
17        }
18
19        // Only the first value remains at index zero.
20        if (index == 0) {
21            return arr[0] == remaining ? 1 : 0;
22        }
23
24        // Skipping preserves the remaining target.
25        int notTaken = solve(index - 1, remaining, arr);
26
27        int taken = 0;
28
29        // Picking is valid only within the remainder.
30        if (arr[index] <= remaining) {
31            // Picking reduces the sum still required.
32            taken = solve(
33                index - 1,
34                remaining - arr[index],
35                arr
36            );
37        }
38
39        // Disjoint pick and skip counts are added.
40        return (notTaken + taken) % modulo;
41    }
42
43public:
44    // Returns the subset count for the target.
45    int countSubsets(vector<int>& arr, int target) {
46        int n = arr.size();
47
48        // The full prefix starts with the full target.
49        return solve(n - 1, target, arr);
50    }
51};
52
53// Driver code
54int main() {
55    vector<int> arr = {2, 3, 5, 16, 8, 10};
56    int target = 10;
57    Solution obj;
58    cout << obj.countSubsets(arr, target);
59    return 0;
60}

Complexity Analysis

Time Complexity: O(2^N), where N is the number of array elements, because every array position can create a pick branch and a skip branch, forming a binary recursion tree.

Space Complexity: O(N), because the deepest recursive path can contain at most one call for each array position.

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Memoization

Different decision paths can reach the same pair (index, remaining). Without memoization, the same state repeats its pick-or-skip work even though it always produces the same count. A two-dimensional dp array stores the answer for each state, avoiding this repeated work.

Memoization keeps the same recursive states and transitions. When a previously calculated state is reached again, its stored count is returned immediately, so each state performs its branch calculations only once.

Algorithm

Start with solve(N - 1, K) because memoization preserves the same initial state as recursion.
Create dp with N rows and K + 1 columns because index and remaining uniquely define each cached state.
Fill dp with -1 because the marker distinguishes uncalculated states from valid counts, including 0.
Return 1 when remaining == 0 because the current selection has formed one valid subset.
Handle the index == 0 case by comparing arr[0] with remaining because only the first element remains available.
Return dp[index][remaining] when a cached value exists because the same state always produces the same count.
Compute the skip and valid pick branches using the same recurrence as recursion because memoization does not change the available choices.
Store the modular sum of both branches in dp[index][remaining] before returning it so future calls can reuse the completed state.

Dry Run

1 / 2

Diagram 1

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5private:
  int modulo = 1000000007;
7
  // Counts subsets and caches repeated states.
  int solve(
      int index,
      int remaining,
      vector<int>& arr,
      vector<vector<int>>& dp
  ) {
      // A zero remainder forms one completed subset.
      if (remaining == 0) {
          return 1;
      }
19
      // Only the first value remains at index zero.
      if (index == 0) {
          return arr[0] == remaining ? 1 : 0;
      }
24
      // A stored state avoids repeated branch work.
      if (dp[index][remaining] != -1) {
          return dp[index][remaining];
      }
29
      // Skipping preserves the remaining target.
      int notTaken = solve(
          index - 1,
          remaining,
          arr,
          dp
      );
37
      int taken = 0;
39
      // Picking is valid only within the remainder.
      if (arr[index] <= remaining) {
          // Picking reduces the sum still required.
          taken = solve(
              index - 1,
              remaining - arr[index],
              arr,
              dp
          );
      }
50
      // The cache stores the modular branch sum.
      dp[index][remaining] = (
          notTaken + taken
      ) % modulo;
55
      // The stored count represents the current state.
      return dp[index][remaining];
  }
59
60public:
  // Returns the subset count for the target.
  int countSubsets(vector<int>& arr, int target) {
      int n = arr.size();
64
      // Negative entries mark uncalculated states.
      vector<vector<int>> dp(
          n,
          vector<int>(target + 1, -1)
      );
70
      // The full prefix starts with the full target.
      return solve(n - 1, target, arr, dp);
  }
74};
75
76// Driver code
77int main() {
  vector<int> arr = {2, 3, 5, 16, 8, 10};
  int target = 10;
  Solution obj;
  cout << obj.countSubsets(arr, target);
  return 0;
83}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of array elements and K is the target sum, because at most N × (K + 1) states are evaluated, with each state performing constant-time branch and merge work.

Space Complexity: O(N × K) + O(N), because the dp table stores all index-and-sum states, while the recursion stack can contain at most N calls.

Tabulation

Memoization solves states only after recursive requests arrive. Tabulation fills the same prefix-and-sum states directly, beginning with the smallest prefix. Every table entry still combines a skipped current value with a picked current value.

Row index - 1 already contains all counts needed for row index. Left-to-right row construction removes the recursion stack while keeping the complete two-dimensional state table.

Algorithm

Create a dp table with n rows and K + 1 columns because every cell represents one prefix and one target sum.
Set dp[index][0] = 1 for every row because the empty selection forms sum 0 from any positive-value prefix.
Set dp[0][arr[0]] = 1 when the first value fits because a single first position forms exactly one positive sum.
Process rows from index 1 onward because row index - 1 must be complete before row index.
Read dp[index - 1][sum] for the skip count because exclusion leaves the requested sum unchanged.
Read dp[index - 1][sum - arr[index]] only after the current value fits because picking requires a nonnegative earlier sum.
Store the modular sum of pick and skip counts because the branches partition every subset represented by the cell.
Return dp[n - 1][K] because the final row and target column represent the complete problem.

Dry Run

count-subsets-sum-k-tabulation-indices-fixed.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
  // Returns the subset count through tabulation.
  int countSubsets(vector<int>& arr, int target) {
      int n = arr.size();
      int modulo = 1000000007;
10
      // Every cell stores one prefix-and-sum count.
      vector<vector<int>> dp(
          n,
          vector<int>(target + 1, 0)
      );
16
      // Every positive-value prefix forms sum zero once.
      for (int index = 0; index < n; index++) {
          dp[index][0] = 1;
      }
21
      // The first value can form one positive sum.
      if (arr[0] <= target) {
          dp[0][arr[0]] = 1;
      }
26
      // Later rows use only the completed earlier row.
      for (int index = 1; index < n; index++) {
          // Positive sums preserve the zero-sum base.
          for (int sum = 1; sum <= target; sum++) {
              // Skipping preserves the requested sum.
              int notTaken = dp[index - 1][sum];
33
              int taken = 0;
35
              // Picking needs a nonnegative earlier sum.
              if (arr[index] <= sum) {
                  // Earlier counts supply the reduced sum.
                  taken = dp[
                      index - 1
                  ][sum - arr[index]];
              }
43
              // Current count merges disjoint choices.
              dp[index][sum] = (
                  notTaken + taken
              ) % modulo;
          }
      }
50
      // The last row covers the complete array.
      return dp[n - 1][target];
  }
54};
55
56// Driver code
57int main() {
  vector<int> arr = {2, 3, 5, 16, 8, 10};
  int target = 10;
  Solution obj;
  cout << obj.countSubsets(arr, target);
  return 0;
63}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of array elements and K is the target sum, because each of the N rows processes all K + 1 possible sums once with constant transition work.

Space Complexity: O(N × K), because the two-dimensional dp table stores one count for every prefix-and-sum state, and no recursion stack is used.

Space Optimization

Every tabulation cell reads values only from the preceding row. Older rows never affect a later transition, so two one-dimensional arrays can replace the full table.

Array previous stores the completed earlier row, and array current stores counts for the active array position. After all sums in current are calculated, assigning current to previous preserves the required row for the next position.

Algorithm

Create previous with K + 1 entries because a single row contains every remaining sum needed by the next position.
Set previous[0] = 1 and initialize the first value because the first row must match the tabulation base.
Build a fresh current row for every later position because partially updated counts must never replace earlier-row values.
Set current[0] = 1 because the empty selection remains the only zero-sum subset for positive values.
Read skip and valid pick counts from previous because both transition terms belong to the completed earlier row.
Calculate current[sum] from the modular branch sum because the active row must preserve the same tabulation recurrence.
Shift current into previous only after every sum is complete because early replacement would mix two different rows.
Return previous[K] because the final shift stores counts for the complete array.

Dry Run

count-subsets-sum-k-space-optimization-indices-fixed.png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    // Returns the count with two rolling rows.
7    int countSubsets(vector<int>& arr, int target) {
8        int n = arr.size();
9        int modulo = 1000000007;
10
11        // The previous row stores all earlier counts.
12        vector<int> previous(target + 1, 0);
13
14        // The empty selection forms sum zero once.
15        previous[0] = 1;
16
17        // The first value can form one positive sum.
18        if (arr[0] <= target) {
19            previous[arr[0]] = 1;
20        }
21
22        // Every later position builds one fresh row.
23        for (int index = 1; index < n; index++) {
24            vector<int> current(target + 1, 0);
25
26            // Positive values preserve one zero-sum choice.
27            current[0] = 1;
28
29            // Every positive sum uses the earlier row.
30            for (int sum = 1; sum <= target; sum++) {
31                // Skipping preserves the requested sum.
32                int notTaken = previous[sum];
33
34                int taken = 0;
35
36                // Picking needs a nonnegative earlier sum.
37                if (arr[index] <= sum) {
38                    // Earlier counts supply the reduced sum.
39                    taken = previous[sum - arr[index]];
40                }
41
42                // Current sum combines skip and pick counts.
43                current[sum] = (
44                    notTaken + taken
45                ) % modulo;
46            }
47
48            // Shift current into previous for the next row.
49            previous = current;
50        }
51
52        // The final rolling row covers the full array.
53        return previous[target];
54    }
55};
56
57// Driver code
58int main() {
59    vector<int> arr = {2, 3, 5, 16, 8, 10};
60    int target = 10;
61    Solution obj;
62    cout << obj.countSubsets(arr, target);
63    return 0;
64}

Complexity Analysis

Time Complexity: O(N × K), where N is the number of array elements and K is the target sum, because every array value processes all K + 1 possible sums once with constant transition work.

Space Complexity: O(K), because only the previous and current rows of length K + 1 are stored, while older rows are discarded.

Interview follow-up Questions

Yes. Array positions define choices, so arr = [2, 2, 2, 2] and K = 4 produce 6 position pairs.

Count Subsets with Sum K Using Dynamic Programming

Example 1

Example 2

Recursion

Algorithm

Dry Run

Solution

Complexity Analysis

Memoization

Algorithm

Dry Run

Solution

Complexity Analysis

Tabulation

Algorithm

Dry Run

Solution

Complexity Analysis

Space Optimization

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Largest Divisible Subset

Best Time to Buy and Sell Stock IV: At Most K Transactions

Best Time to Buy and Sell Stock with Transaction Fee