Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Count Subset With Target Sum

HARDProblemSolveExternal Links

Description

Given an array arr[] of non-negative integers and an integer target, count the number of subsets of the array whose elements sum to exactly target.

A subset is any selection of zero or more elements from the array. Two subsets are considered different if they consist of elements at different indices, even if the values are the same.

Key observations:

  • Every element has two choices: include it in the subset or exclude it.
  • Elements may be duplicated — identical values at different positions count as distinct choices.
  • The empty subset has a sum of 0. If target = 0, the empty subset is always one valid answer.
  • All elements are non-negative, so once a partial sum exceeds target, no further inclusions can bring it back down.

Examples

Example 1

Input: arr = [1, 2, 3, 3], target = 6

Output: 3

Explanation:
The three subsets that sum to 6 are:

  • {1, 2, 3} using the 3 at index 2 → 1 + 2 + 3 = 6
  • {1, 2, 3} using the 3 at index 3 → 1 + 2 + 3 = 6
  • {3, 3} using both 3s → 3 + 3 = 6

Note: although the first two subsets look identical, they pick different elements (index 2 vs. index 3), so they count as separate subsets.

Example 2

Input: arr = [5, 2, 3, 10, 6, 8], target = 10

Output: 3

Explanation:
The three subsets that sum to 10:

  • {5, 2, 3} → 5 + 2 + 3 = 10
  • {2, 8} → 2 + 8 = 10
  • {10} → 10 = 10

Subsets can have different sizes; what matters is that the sum equals the target.

Example 3

Input: arr = [5, 7, 8], target = 3

Output: 0

Explanation:
Every element is larger than 3, so no non-empty subset can sum to 3, and the empty subset sums to 0. Therefore the count is 0.

Constraints

  • 1 ≤ arr.length ≤ 10^3
  • 0 ≤ arr[i] ≤ 10^3
  • 0 ≤ target ≤ 10^3

Editorial

Brute Force

Intuition

The most natural way to count subsets: try every possible subset and count those whose sum equals the target.

Think of it as standing before each element and making a binary choice — include it or exclude it. After making a choice for every element, you have a subset. Check if its sum matches the target.

With n elements, there are 2^n possible subsets. We recursively explore both choices for each element:

  • Include arr[i]: add it to the running sum and move to index i + 1.
  • Exclude arr[i]: keep the sum unchanged and move to index i + 1.

When we've processed all elements (i == n), we check: does the accumulated sum equal target? If yes, count this subset.

Step-by-Step Explanation

Let us trace Example 1: arr = [1, 2, 3, 3], target = 6.

There are 2^4 = 16 subsets. We explore them via DFS (include/exclude decisions):

Subset {1,2,3,3} (all elements): sum = 1+2+3+3 = 9 ≠ 6. Too large.

Subset {1,2,3} (indices 0,1,2): sum = 6 = target ✓. Match #1!

Subset {1,2,3} (indices 0,1,3): sum = 6 = target ✓. Match #2! Same values but different index chosen.

Subset {1,2} (indices 0,1): sum = 3 ≠ 6. Too small — with only 2 small elements, we can't reach 6.

Subset {1,3,3} (indices 0,2,3): sum = 7 ≠ 6. Overshoots by 1.

Subset {3,3} (indices 2,3): sum = 6 = target ✓. Match #3!

Subset {} (empty): sum = 0 ≠ 6.

… (other subsets also fail to sum to 6)

Result: 3 subsets found out of 16 total. We had to check all 16.

Brute Force — Explore All 2^n Subsets via Recursion — Watch the recursive exploration of all subsets by including or excluding each element. Green highlights mark elements included in the current subset. Three subsets match target = 6.

Algorithm

  1. Define a recursive function count(idx, currSum) where idx is the current index and currSum is the running sum of the current subset.
  2. Base case: If idx == n, return 1 if currSum == target, else 0.
  3. Recursive step:
    • include = count(idx + 1, currSum + arr[idx]) — include arr[idx].
    • exclude = count(idx + 1, currSum) — skip arr[idx].
    • Return include + exclude.
  4. Call count(0, 0) and return the result.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int perfectSum(vector<int>& arr, int target) {
        return count(arr, 0, 0, target);
    }

private:
    int count(vector<int>& arr, int idx, int currSum, int target) {
        if (idx == (int)arr.size())
            return currSum == target ? 1 : 0;

        // Include arr[idx]
        int include = count(arr, idx + 1, currSum + arr[idx], target);
        // Exclude arr[idx]
        int exclude = count(arr, idx + 1, currSum, target);

        return include + exclude;
    }
};
class Solution:
    def perfectSum(self, arr: list[int], target: int) -> int:
        def count(idx: int, curr_sum: int) -> int:
            if idx == len(arr):
                return 1 if curr_sum == target else 0
            # Include arr[idx] or exclude it
            return (count(idx + 1, curr_sum + arr[idx])
                    + count(idx + 1, curr_sum))

        return count(0, 0)
class Solution {
    public int perfectSum(int[] arr, int target) {
        return count(arr, 0, 0, target);
    }

    private int count(int[] arr, int idx, int currSum, int target) {
        if (idx == arr.length)
            return currSum == target ? 1 : 0;

        int include = count(arr, idx + 1, currSum + arr[idx], target);
        int exclude = count(arr, idx + 1, currSum, target);

        return include + exclude;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

Every element has 2 choices (include / exclude), giving 2^n total subsets to explore. Each leaf of the recursion tree does O(1) work. There are 2^n leaves, so the total work is O(2^n).

For the constraint n ≤ 1000, 2^1000 is a number with over 300 digits — utterly impossible.

Space Complexity: O(n)

The recursion stack goes at most n levels deep (one level per element). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force generates 2^n subsets. With n up to 1000, 2^1000 subsets is beyond computation — it is an unfathomably large number, far exceeding the number of atoms in the observable universe (~10^80).

But there is a deeper reason the brute force wastes work: overlapping subproblems. Consider arr = [1, 1, 2, 3] with target = 4. The recursive call count(2, 2) (meaning: "starting at index 2, we need a remaining sum of 2") gets computed multiple times:

  • Once from the path: include arr[0]=1, include arr[1]=1 → currSum = 2, continue from index 2.
  • Once from the path: include arr[0]=1, exclude arr[1]=1 (oh wait, arr[1]=1 so currSum=1), then... Actually with arr=[1,1,2,3], including first 1 and excluding second (sum=1) vs excluding first 1 and including second (sum=1) both lead to count(2, 1) — the same subproblem!

These duplicate computations multiply as the array grows. The recursion tree has exponential width, but the number of distinct subproblems is only n × (target + 1) — because the state is fully determined by the current index i (0 to n) and the current sum (0 to target). This is at most 1000 × 1001 ≈ 10^6 — a million instead of 2^1000.

Key insight: If we cache the result for each (i, currSum) pair (Dynamic Programming), we solve each subproblem only once, reducing the time from O(2^n) to O(n × target).

Optimal Approach - Dynamic Programming

Intuition

We reformulate the recursion as a bottom-up DP table. Define:

dp[i][j] = number of subsets of arr[0..i-1] (the first i elements) that sum to exactly j.

Base case: dp[0][0] = 1 — the empty subset (choosing 0 elements from 0 elements) has sum 0. For all other j > 0, dp[0][j] = 0 — no elements means no way to reach a positive sum.

Transition: For each element arr[i-1], we have two choices:

  • Exclude it: The count is dp[i-1][j] (same count without this element).
  • Include it: Only if j ≥ arr[i-1]. The count is dp[i-1][j - arr[i-1]] (subsets from the first i-1 elements that sum to the remainder).

So: dp[i][j] = dp[i-1][j] + dp[i-1][j - arr[i-1]] (when j ≥ arr[i-1]), or just dp[i][j] = dp[i-1][j] otherwise.

The answer is dp[n][target].

This builds up from smaller subproblems: first considering only element 0, then elements 0-1, then 0-2, etc., and for each prefix, tracking how many subsets sum to each value from 0 to target.

Step-by-Step Explanation

Trace Example 1: arr = [1, 2, 3, 3], target = 6.

We build a table with 5 rows (i = 0..4) and 7 columns (j = 0..6).

Row 0 (base): dp[0][0] = 1. All other dp[0][j] = 0.

Row 1 (process arr[0] = 1):

  • j = 0: dp[0][0] = 1 (exclude 1). dp[1][0] = 1.
  • j = 1: dp[0][1] + dp[0][0] = 0 + 1 = 1 (include 1). dp[1][1] = 1.
  • j ≥ 2: dp[1][j] = 0.
    → Row 1: [1, 1, 0, 0, 0, 0, 0]

Row 2 (process arr[1] = 2):

  • j = 2: dp[1][2] + dp[1][0] = 0 + 1 = 1 (include 2, one way: {2}).
  • j = 3: dp[1][3] + dp[1][1] = 0 + 1 = 1 (include 2 with 1: {1,2}).
    → Row 2: [1, 1, 1, 1, 0, 0, 0]

Row 3 (process arr[2] = 3, the first 3):

  • j = 3: dp[2][3] + dp[2][0] = 1 + 1 = 2. Two ways to sum to 3: {1,2} and {3}. This is the first time a cell exceeds 1!
  • j = 4: dp[2][4] + dp[2][1] = 0 + 1 = 1.
  • j = 5: dp[2][5] + dp[2][2] = 0 + 1 = 1.
  • j = 6: dp[2][6] + dp[2][3] = 0 + 1 = 1.
    → Row 3: [1, 1, 1, 2, 1, 1, 1]

Row 4 (process arr[3] = 3, the second 3):

  • j = 3: dp[3][3] + dp[3][0] = 2 + 1 = 3.
  • j = 6: dp[3][6] + dp[3][3] = 1 + 2 = 3. This is our answer!
    → Row 4: [1, 1, 1, 3, 2, 2, 3]

Result: dp[4][6] = 3.

Bottom-Up DP Table — Building Subset Counts Row by Row — Watch the 2D DP table fill row by row. Each row adds one more element to the available pool. The final cell dp[4][6] gives the answer: 3 subsets sum to 6.

Algorithm

  1. Create a 2D array dp[n+1][target+1] initialized to 0. Set dp[0][0] = 1.
  2. For each element i from 1 to n:
    • For each sum j from 0 to target:
      • dp[i][j] = dp[i-1][j] (exclude arr[i-1]).
      • If j >= arr[i-1]: dp[i][j] += dp[i-1][j - arr[i-1]] (include arr[i-1]).
  3. Return dp[n][target].

Space Optimization: Since row i only depends on row i-1, we can use a single 1D array and iterate j from right to left:

  1. Create dp[target+1] initialized to 0. Set dp[0] = 1.
  2. For each element x in arr:
    • For j from target down to x: dp[j] += dp[j - x].
  3. Return dp[target].

Why right-to-left? We must use the old (pre-update) values of dp[j - x]. Iterating left-to-right would use already-updated values, effectively allowing an element to be included multiple times (unbounded knapsack), which is incorrect.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int perfectSum(vector<int>& arr, int target) {
        int n = arr.size();
        // 2D DP table: dp[i][j] = subsets of first i elements summing to j
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        dp[0][0] = 1; // base: empty subset sums to 0

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j]; // exclude arr[i-1]
                if (j >= arr[i - 1])
                    dp[i][j] += dp[i - 1][j - arr[i - 1]]; // include
            }
        }
        return dp[n][target];
    }
};
class Solution:
    def perfectSum(self, arr: list[int], target: int) -> int:
        n = len(arr)
        # dp[i][j] = count of subsets of arr[0..i-1] summing to j
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1  # base: empty subset sums to 0

        for i in range(1, n + 1):
            for j in range(target + 1):
                dp[i][j] = dp[i - 1][j]  # exclude arr[i-1]
                if j >= arr[i - 1]:
                    dp[i][j] += dp[i - 1][j - arr[i - 1]]  # include

        return dp[n][target]
class Solution {
    public int perfectSum(int[] arr, int target) {
        int n = arr.length;
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1; // base: empty subset sums to 0

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j]; // exclude arr[i-1]
                if (j >= arr[i - 1])
                    dp[i][j] += dp[i - 1][j - arr[i - 1]]; // include
            }
        }
        return dp[n][target];
    }
}

Space Optimization

Since each row dp[i] depends only on the previous row dp[i-1], we can compress the 2D table into a single 1D array. The trick is to iterate j from right to left (from target down to arr[i-1]), so that when we access dp[j - arr[i-1]], it still holds the value from the previous row (not yet overwritten in this pass).

This reduces space from O(n × target) to just O(target).

#include <vector>
using namespace std;

class Solution {
public:
    int perfectSum(vector<int>& arr, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int x : arr) {
            for (int j = target; j >= x; j--) {
                dp[j] += dp[j - x];
            }
        }
        return dp[target];
    }
};
class Solution:
    def perfectSum(self, arr: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for x in arr:
            for j in range(target, x - 1, -1):
                dp[j] += dp[j - x]

        return dp[target]
class Solution {
    public int perfectSum(int[] arr, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int x : arr) {
            for (int j = target; j >= x; j--) {
                dp[j] += dp[j - x];
            }
        }
        return dp[target];
    }
}

Complexity Analysis

Time Complexity: O(n × target)

We fill a table of n rows and (target + 1) columns. Each cell is computed in O(1). For the maximum constraints (n = 1000, target = 1000): 1000 × 1001 ≈ 10^6 operations — very fast.

Space Complexity:

  • 2D version: O(n × target) for the full DP table.
  • Space-optimized 1D version: O(target) — only a single array of length target + 1.

The 1D version is preferred in practice since it uses minimal memory while maintaining the same time complexity.