What is the brute force approach and complexity for Count Subsets with Sum?

Recurse on each number: leave it out or take it in; count the paths that end at the target with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Count Subsets with Sum?

Keep one row dp[s]; for each number add dp[s − x] into dp[s], going from the target down to x with optimal time complexity O(N · X) and space complexity O(X).

How do you identify the pattern for Count Subsets with Sum?

Look for key signals in the prompt: "count the subsets" indicates The answer is a number of ways, not a yes or no. Add the ways together; do not take a max or OR.; "numbers that add up to target" indicates Each number is a 0/1 choice: in or out. The chosen numbers must sum to target.; "each number can be used at most once" indicates Each item is used once, so the sum loop goes high → low, as in 0/1 Knapsack..

Count Subsets with Sum

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelDP — Knapsack, Count ways (0/1 count)

Complexity:O(2^N)→O(N · X)

Key Insight

Keep one row dp[s] for every sum. For each number x, run dp[s] += dp[s − x] for s from target down to x. Going downward means dp[s − x] is still the count from before x was used, so each number is used at most once.

Core Validity Invariant

dp[s − x] must be the count from before x was used. That is why s goes from high to low: then every cell we read is still the old value.

Problem

You get an array arr of numbers and a number target. Count the subsets whose numbers add up to exactly target.

A subset is picked by position. Each number is either in the subset or out of it. So [1, 1] has two different subsets with sum 1: one for each 1. The empty subset counts too, and its sum is 0.

Return the count. GFG's function returns an int and its tests keep the count small enough; the code here also takes the count modulo 10^9 + 7 so that big inputs (many zeros double the count each time) can never overflow.

Input

arr, a list of non-negative integers (zeros are allowed), and target, an integer.

Output

The number of subsets whose sum is target.

Example 1

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

Output: 3

The subsets {5, 2, 3}, {2, 8} and {10} add up to 10.

Example 2

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

Output: 4

The subsets are {3}, {1, 2}, {0, 3} and {0, 1, 2}. The zero can join any subset without changing its sum, so it doubles the count.

Example 3

Input: arr = [1, 1], target = 1

Output: 2

Each 1 sits at its own position, so {first 1} and {second 1} are two different subsets.

Example 4

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

Output: 3

The subsets are {1, 2, first 3}, {1, 2, second 3} and {first 3, second 3}.

Constraints

• 1 ≤ arr.size() ≤ 10^3
• 0 ≤ arr[i], target ≤ 10^3

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I add a 0 to a subset, does its sum change? What does that do to the count?
2.
For one number, how many choices do I have? For N numbers, how many subsets are there in total?
3.
If I split the subsets that reach sum s by whether they contain the last number, what do I know about each group?
4.
Am I asked whether a subset exists, or how many subsets exist? Does that change what each cell should store?
5.
When I process the numbers one at a time, which earlier results do I still need after I finish a number?

Brute force approach

Idea

Each number is either in the subset or out of it. Walk the numbers in order and make that choice for each one. When the last number is decided, check whether the taken numbers add up to target. Every subset is exactly one path, so the number of paths that hit the target is the answer.

Thinking process

1
A subset is decided by one yes or no for each number. With 4 numbers that is 2 · 2 · 2 · 2 = 16 subsets.
2
Take arr = [1, 2, 3, 0] and target 3. Out, out, in, out gives {3}: sum 3, so it counts. In, out, in, out gives {1, 3}: sum 4, so it does not.
3
Stop a path when the sum has gone over the target. Remaining goes below 0, and adding more numbers can only make it worse.
4
The zero is decided yes or no like every other number, so {3} and {0, 3} are two different paths and both count.

Visual

Circle = the sum still needed (remaining). Rows are indexes (L0 = before arr[0]). Blue = the current path. Orange = the same (index, remaining) was already solved on another branch, so a memo would reuse it. Purple = a subset that hits the target. Red = the sum went below 0.

Brute force: include or exclude every numberarr = [1, 1, 2], target = 2step 1/23

tree

arr

▲i

taken

Subsets that hit the target

none yet

State

i: 0
remaining: 2
calls: 1

index 0, remaining 2: try leaving 1 out, then taking it in

Two choices for arr[0] = 1: skip it, or take it.

Code & Implementation

brute.cpp

class Solution {
    static constexpr long long MOD = 1000000007LL;

    // At each index we either leave the number out or take it in.
    // Returns how many ways the numbers from index i on can make `remaining`.
    long long ways(vector<int>& arr, int i, int remaining) {
        if (remaining < 0) return 0;                              // this choice already went over
        if (i == (int)arr.size()) return remaining == 0 ? 1 : 0;  // one full subset: counts only if it hits the target
        long long left_out = ways(arr, i + 1, remaining);         // skip arr[i]
        long long taken_in = ways(arr, i + 1, remaining - arr[i]); // take arr[i]
        return (left_out + taken_in) % MOD;
    }

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

Complexity

Time O(2^N)Space O(N)

Each number doubles the number of paths, so N numbers give 2^N paths. The space is the recursion, which is N calls deep. The same (index, remaining) pair is solved on many paths.

Better approach

Why brute force is slow

The brute force starts from the top again for every path, so a state like (index 2, remaining 1) is solved again each time a different path reaches it.

What repeated work are we doing?

Different include / exclude paths reach the same index with the same remaining sum. In the brute visual, index 2 with remaining 1 is solved twice.

What information can we reuse?

A table cell dp[i][s] holds the answer for one (index, sum) pair. Each cell is computed once, from two cells in the row above.

New approach

Idea

Let dp[i][s] be the number of subsets of the first i numbers whose sum is s. A subset of the first i numbers either leaves out number i, which is counted by dp[i − 1][s], or takes it in, which is counted by dp[i − 1][s − arr[i − 1]]. These two groups never overlap, so we add them.

Thinking process

1
The brute force solves the same (index, remaining) pair again on another path. A table stores each pair once.
2
Take arr = [1, 2] and target 2. Row 0 is [1, 0, 0]: only the empty subset, which has sum 0.
3
After the number 1, row 1 is [1, 1, 0]: the empty subset (sum 0) and {1} (sum 1).
4
After the number 2, dp[2][2] = dp[1][2] + dp[1][0] = 0 + 1 = 1. The 0 means leaving 2 out gives nothing for sum 2. The 1 is the empty subset plus 2, which is {2}.

Code & Implementation

better.cpp

class Solution {
    static constexpr long long MOD = 1000000007LL;

public:
    int perfectSum(vector<int>& arr, int target) {
        if (target < 0) return 0;
        int n = arr.size();
        // dp[i][s] = number of subsets of the first i numbers whose sum is s.
        vector<vector<long long>> dp(n + 1, vector<long long>(target + 1, 0));
        dp[0][0] = 1;                                              // only the empty subset, sum 0
        for (int i = 1; i <= n; i++) {
            int x = arr[i - 1];
            for (int s = 0; s <= target; s++) {
                dp[i][s] = dp[i - 1][s];                           // arr[i-1] left out
                if (s >= x) {                                      // arr[i-1] taken in
                    dp[i][s] = (dp[i][s] + dp[i - 1][s - x]) % MOD;
                }
            }
        }
        return (int)dp[n][target];
    }
};

Complexity

Time O(N · X)Space O(N · X)

X is the target. The table has N + 1 rows and X + 1 columns, and each cell takes one or two additions. It stores more than needed: a row only reads the row above it, so one row is enough.

Optimized approach

Idea

Start from brute force

Brute force walks every include / exclude path, so the same (index, remaining) pair is solved many times.

Find the repeated work

The table shows the repeated states are a row-by-row build. Each row reads only the row above, so a single row is enough.

Define the state — what variables do I need?

dp[s]: The number of subsets, from the numbers seen so far, whose sum is s. dp[0] starts at 1, for the empty subset.
x: The number being added in this round.
s: The sum being updated, from target down to x.

Define validity

dp[s − x] must be the count from before x was used. That is why s goes from high to low: then every cell we read is still the old value.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

dp[0] = 1, all other cells 0

The empty subset is the only way to reach sum 0 before any number is seen.

For each number x, s from target down to x

dp[s] += dp[s − x]

The subsets with sum s that take x in are the subsets with sum s − x before x, plus x. Those subsets are added to the ones that leave x out, which are already in dp[s].

x = 0

The same line: dp[s] += dp[s]

A zero is in or out of every subset, so every count doubles. No special case is needed.

What does the current window add to the answer?

Each number adds the subsets that take it in. After all numbers are processed, dp[target] counts every subset with the target sum.

Code & Implementation

optimal.cpp

class Solution {
    static constexpr long long MOD = 1000000007LL;

public:
    int perfectSum(vector<int>& arr, int target) {
        if (target < 0) return 0;
        // dp[s] = number of subsets (of the numbers seen so far) whose sum is s.
        vector<long long> dp(target + 1, 0);
        dp[0] = 1;                                                 // the empty subset has sum 0
        for (int x : arr) {
            // s goes high → low, so dp[s - x] still holds the count from BEFORE this number.
            // With x = 0 the update is dp[s] += dp[s]: every subset can take the zero or not, so counts double.
            for (int s = target; s >= x; s--) {
                dp[s] = (dp[s] + dp[s - x]) % MOD;
            }
        }
        return (int)dp[target];
    }
};

Complexity

Time O(N · X)Space O(X)

X is the target. The row has X + 1 cells, and each number scans the row once from the target down to x. N is the number of numbers. A zero needs no special case: dp[s] += dp[s] doubles the count.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse on each number: leave it out or take it in; count the paths that end at the target	O(2^N)	O(N)
Better	dp[i][s] counts the subsets of the first i numbers that sum to s; each cell reads two cells above	O(N · X)	O(N · X)
Optimal	Keep one row dp[s]; for each number add dp[s − x] into dp[s], going from the target down to x	O(N · X)	O(X)

Why does this belong to this pattern?

Clues in the problem statement

“count the subsets”The answer is a number of ways, not a yes or no. Add the ways together; do not take a max or OR.
“numbers that add up to target”Each number is a 0/1 choice: in or out. The chosen numbers must sum to target.
“each number can be used at most once”Each item is used once, so the sum loop goes high → low, as in 0/1 Knapsack.

Choose a subset (each number in or out)+sum equals target+count every subset, not just check one→DP — Knapsack, Count ways (0/1 count)

This is the anchor of Count ways. It uses the same 0/1 table as Subset Sum, but each cell adds counts with + where Subset Sum asks yes or no with OR. The loop order is the same as 0/1 Knapsack: sums go from high to low. Target Sum and Profitable Schemes change what the sum or the state means, but they keep this adding rule.

Don't make this mistake

Pattern confusion: OR or max instead of +

✗ dp[s] = dp[s] || dp[s - x];

✓ dp[s] = dp[s] + dp[s - x];

The OR line is the yes/no Subset Sum table. On arr = [1, 2, 3, 0] with target 3, the OR version ends with true, so it returns 1, not 4. A count needs the cells added.

Pattern confusion: sums going low → high

✗ for (int s = x; s <= target; s++) dp[s] += dp[s - x];

✓ for (int s = target; s >= x; s--) dp[s] += dp[s - x];

Going up lets dp[s − x] already include x, so x is used again. This is the unbounded Knapsack loop. On arr = [1, 2, 3, 0] with target 3, it returns 6, not 4.

Skipping zeros

✗ if (x == 0) continue;

✓ No special case. The normal loop gives dp[s] += dp[s].

A zero can be in or out of every subset, so every count must double. On arr = [1, 2, 3, 0] with target 3, skipping the zero returns 2, not 4.

Forgetting the empty subset

✗ vector<long long> dp(target + 1, 0);

✓ dp[0] = 1; // the empty subset has sum 0

With every cell at 0, nothing is ever added, so the answer is 0 for every input. The empty subset is what starts every count.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture