Log inSign up
mediumGeeksforGeeksNot Started

Count of Subsets with Given Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array arr of non-negative integers and an integer sum, determine the number of subsets of the array whose elements add up to exactly sum.

Since the answer may be very large, return it modulo 109 + 7 (or exact count if within 64-bit bounds).

Note: Each element in the array can be used at most once in any subset. Zeros in the array are allowed and can lead to multiple valid subsets (e.g., adding 0 to any valid subset produces another valid subset).

### Example 1 - Input: arr = [1, 2, 3, 3], sum = 6 - Output: 3 - Explanation: The subsets with sum 6 are: 1. [1, 2, 3] (first 3) 2. [1, 2, 3] (second 3) 3. [3, 3] -> wait: 1+2+3=6, 1+2+3=6, 3+3=6. Total = 3.

### Example 2 - Input: arr = [1, 1, 1, 1], sum = 1 - Output: 4 - Explanation: Any single element forms sum 1 (4 subsets).

### Example 3 - Input: arr = [0, 0, 1], sum = 1 - Output: 4 - Explanation: [1], [0, 1], [0, 1], [0, 0, 1].

Constraints:

  • 1 <= arr.length <= 1000
  • 0 <= arr[i] <= 1000
  • 0 <= sum <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate the 0/1 counting recurrence relation.
  • Properly handle zeros in the input without corrupting base cases.
  • Optimize 2D state matrix to a single backward 1D array with modulo arithmetic.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding total number of subsets summing to a target value.
  • Each array item can be used at most once (0/1).
  • Array may contain zeros.

Algorithmic Decision Tree:

  • 0/1 constraint -> Reverse iteration in 1D array.
  • Counting subsets -> Add ways from exclude (dp[s]) and include (dp[s - arr[i]]).

Connected Patterns:

0/1 KnapsackSubset SumTarget SumPartition Equal Subset Sum

1. Recursive Exhaustive Search (Include/Exclude)

Intuition

At each index from 0 to n-1, branch into taking the element or skipping it.

Algorithm

  1. Define dfs(i, currentSum).
  2. If i == arr.length: return currentSum == target ? 1 : 0.
  3. Option 1: skip dfs(i + 1, currentSum).
  4. Option 2: take dfs(i + 1, currentSum + arr[i]).
  5. Return Option 1 + Option 2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int dfs(int i, int currentSum, int target, const vector<int>& arr) {
7 if (i == (int)arr.size()) {
8 return currentSum == target ? 1 : 0;
9 }
10 int skip = dfs(i + 1, currentSum, target, arr);
11 int take = dfs(i + 1, currentSum + arr[i], target, arr);
12 return skip + take;
13}
14
15int countSubsetsRec(const vector<int>& arr, int sum) {
16 return dfs(0, 0, sum, arr);
17}
18
19int main() {
20 vector<int> arr = {1, 2, 3, 3};
21 int sum = 6;
22 cout << "Subsets with sum " << sum << " (Recursive): " << countSubsetsRec(arr, sum) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. 2D Dynamic Programming Tabulation

Intuition

Build table dp[n + 1][sum + 1] where dp[i][s] is the count of subsets using a prefix of i elements that sum to s.

Algorithm

  1. Create dp of size (n + 1) x (sum + 1) filled with 0.
  2. dp[0][0] = 1.
  3. For i = 1 to n:
  4. For s = 0 to sum:
  5. dp[i][s] = dp[i - 1][s]
  6. If arr[i - 1] <= s:
  7. dp[i][s] = (dp[i][s] + dp[i - 1][s - arr[i - 1]]) % MOD
  8. Return dp[n][sum].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int countSubsets2D(const vector<int>& arr, int sum) {
7 int n = arr.size();
8 const int MOD = 1e9 + 7;
9 vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
10 dp[0][0] = 1;
11
12 for (int i = 1; i <= n; i++) {
13 for (int s = 0; s <= sum; s++) {
14 dp[i][s] = dp[i - 1][s];
15 if (arr[i - 1] <= s) {
16 dp[i][s] = (dp[i][s] + dp[i - 1][s - arr[i - 1]]) % MOD;
17 }
18 }
19 }
20 return dp[n][sum];
21}
22
23int main() {
24 vector<int> arr = {1, 2, 3, 3};
25 int sum = 6;
26 cout << "Subsets (2D DP): " << countSubsets2D(arr, sum) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n * sum)
  • Space complexity: O(n * sum) table

3. Space-Optimized 1D Backward Tabulation

Intuition

Maintain a single array dp of size sum + 1. For each element, iterate capacity s backwards from sum down to num.

Algorithm

  1. Create array dp of size sum + 1 filled with 0.
  2. dp[0] = 1.
  3. For each num in arr:
  4. For s = sum down to num:
  5. dp[s] = (dp[s] + dp[s - num]) % MOD.
  6. Return dp[sum].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int countSubsetsOptimal(const vector<int>& arr, int sum) {
7 const int MOD = 1e9 + 7;
8 vector<int> dp(sum + 1, 0);
9 dp[0] = 1;
10
11 for (int num : arr) {
12 for (int s = sum; s >= num; s--) {
13 dp[s] = (dp[s] + dp[s - num]) % MOD;
14 }
15 }
16 return dp[sum];
17}
18
19int main() {
20 vector<int> arr = {1, 2, 3, 3};
21 int sum = 6;
22 cout << "Subsets (Optimal 1D DP): " << countSubsetsOptimal(arr, sum) << endl;
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(n * sum)
  • Space complexity: O(sum) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Include/Exclude DFSO(2^n)O(n)Exhaustive branching over every element.Redundant states
2.2D TabulationO(n * sum)O(n * sum)dp[i][s] table storing prefix subset counts.Table memory
3.1D Backward TabulationOptimalO(n * sum)O(sum)1D array updated in reverse from sum down to num.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Looping forward in 1D array: turns 0/1 knapsack into unbounded knapsack, reusing the same element infinitely.

Pitfall 2:

Incorrectly stopping inner loop at 1 instead of 0 when num == 0 (must allow s to update down to 0).

Crucial Edge Cases to Validate:

  • sum = 0 and array has zeros: Empty subset plus any subset of zeros will sum to 0 (yields 2k subsets).
  • All elements greater than sum: Output is 0 (or 1 if sum is 0 and empty set allowed).
  • Single element equals sum: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify if elements can be zero! Handling zeros properly is the #1 trick in this problem and demonstrates rigorous edge case mastery.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How do elements with value 0 affect the number of subsets with sum S in an array?

Back to DSA Sheet