Problem

Given a set of non-negative integers S and a target value V, count the number of distinct subsets of S whose elements sum to V.

Examples

Example 1

1
2
3

Input: S = [2, 3, 5], V = 7
Output: 1
Explanation: only subset [2,5] sums to 7.
Similar Problems

Solution

We show three approaches: plain recursion (exponential), recursion with memoization (top-down DP), and an iterative bottom-up DP (tabulation). The bottom-up DP is the recommended solution in practice for moderate V.

Method 1 — Recursive backtracking (brute force)

Intuition

Each element can be either included or excluded. Explore both choices recursively and count how many branches reach sum == 0.

Approach

  • Define count(i, rem) = number of subsets from items 0..i that sum to rem.
  • Recurrence:
    • if rem == 0: return 1 (empty subset).
    • if i < 0 or rem < 0: return 0.
    • otherwise return count(i-1, rem - S[i]) + count(i-1, rem).
  • Call count(n-1, V).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
 public:
  // Naive recursive backtracking: O(2^n) time
  int countSubsets(const std::vector<int>& a, int V) {
    return rec(a, (int)a.size() - 1, V);
  }

 private:
  int rec(const std::vector<int>& a, int i, int rem) {
    if (rem == 0) return 1;
    if (rem < 0 || i < 0) return 0;
    // exclude
    int ans = rec(a, i - 1, rem);
    // include
    ans += rec(a, i - 1, rem - a[i]);
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

// Naive recursive backtracking (exponential)
func countSubsets(a []int, V int) int {
  var rec func(int,int) int
  rec = func(i int, rem int) int {
    if rem == 0 { return 1 }
    if rem < 0 || i < 0 { return 0 }
    // exclude
    ans := rec(i-1, rem)
    // include
    ans += rec(i-1, rem-a[i])
    return ans
  }
  return rec(len(a)-1, V)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  // Naive recursive backtracking
  public int countSubsets(int[] a, int V) {
    return rec(a, a.length - 1, V);
  }

  private int rec(int[] a, int i, int rem) {
  if (rem == 0) return 1;
  if (rem < 0 || i < 0) return 0;
  int ans = rec(a, i - 1, rem); // exclude
  ans += rec(a, i - 1, rem - a[i]); // include
  return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
  # Naive recursive backtracking
  def countSubsets(self, a: list[int], V: int) -> int:
    def rec(i: int, rem: int) -> int:
      if rem == 0:
        return 1
      if rem < 0 or i < 0:
        return 0
      ans = rec(i - 1, rem)  # exclude
      ans += rec(i - 1, rem - a[i])  # include
      return ans

    return rec(len(a) - 1, V)

Complexity

  • ⏰ Time complexity: O(2^n) in the worst case — each element branches into include/exclude.
  • 🧺 Space complexity: O(n) recursion depth.

Method 2 — Top-down DP with memoization

Intuition

Many recursive subproblems repeat: count(i, rem) is called multiple times with the same parameters. Cache results in a map keyed by (i, rem) to avoid recomputation.

Approach

  • Use a dictionary memo[(i, rem)] storing the count for that state.
  • Same recurrence as Method 1, but consult memo first.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
 public:
  int countSubsets(const std::vector<int>& a, int V) {
    memo.clear();
    return dfs(a, V, (int)a.size() - 1);
  }

 private:
  std::unordered_map<long long,int> memo; // key = (rem<<32) | i

  int dfs(const std::vector<int>& a, int rem, int i) {
    if (rem == 0) return 1;
    if (rem < 0 || i < 0) return 0;
    long long key = ((long long)rem << 32) | (unsigned int)i;
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;
    int ans = dfs(a, rem, i - 1);
    if (rem >= a[i]) ans += dfs(a, rem - a[i], i - 1);
    memo[key] = ans;
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

package main

func countSubsets(a []int, V int) int {
  memo := make(map[int]int)
  var dfs func(int,int) int
  dfs = func(i int, rem int) int {
    key := (rem<<16) ^ i
    if v, ok := memo[key]; ok { return v }
    if rem == 0 { return 1 }
    if rem < 0 || i < 0 { return 0 }
    ans := dfs(i-1, rem)
    if rem >= a[i] { ans += dfs(i-1, rem-a[i]) }
    memo[key] = ans
    return ans
  }
  return dfs(len(a)-1, V)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
  private Map<String,Integer> memo;

  public int countSubsets(int[] a, int V) {
    memo = new HashMap<>();
    return dfs(a, V, a.length - 1);
  }

  private int dfs(int[] a, int rem, int i) {
    if (rem == 0) return 1;
    if (rem < 0 || i < 0) return 0;
    String key = rem + ":" + i;
    if (memo.containsKey(key)) return memo.get(key);
    int ans = dfs(a, rem, i - 1);
    if (rem >= a[i]) ans += dfs(a, rem - a[i], i - 1);
    memo.put(key, ans);
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
  def countSubsets(self, a: list[int], V: int) -> int:
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(i: int, rem: int) -> int:
      if rem == 0:
        return 1
      if rem < 0 or i < 0:
        return 0
      ans = dfs(i - 1, rem)
      if rem >= a[i]:
        ans += dfs(i - 1, rem - a[i])
      return ans

    return dfs(len(a) - 1, V)

Complexity

  • ⏰ Time complexity: O(n * V) in typical cases because memoization limits states to n * V unique (i, rem) pairs.
  • 🧺 Space complexity: O(n * V) for the memo table plus recursion stack.

Method 3 — Bottom-up DP (tabulation)

Intuition

Build a DP table dp[i][s] = number of ways to make sum s using first i elements. Transition: include/exclude current element.

Approach

  • Initialize dp[0][0] = 1 (one way to make sum 0 with zero elements).
  • Iterate items and sums, update counts.
  • Answer is dp[n][V].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  // Bottom-up DP (1D optimized)
  int countSubsets(const std::vector<int>& a, int V) {
    std::vector<long long> dp(V+1, 0);
    dp[0] = 1;
    for (int num : a) {
      for (int s = V; s >= num; --s) dp[s] += dp[s - num];
    }
    return (int)dp[V];
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package main

// Bottom-up DP (1D optimized)
func countSubsets(a []int, V int) int {
  dp := make([]int, V+1)
  dp[0] = 1
  for _, num := range a {
    for s := V; s >= num; s-- {
      dp[s] += dp[s-num]
    }
  }
  return dp[V]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
  // Bottom-up DP (1D optimized)
  public int countSubsets(int[] a, int V) {
    int[] dp = new int[V+1];
    dp[0] = 1;
    for (int num : a) {
      for (int s = V; s >= num; --s) dp[s] += dp[s - num];
    }
    return dp[V];
  }
}
1
2
3
4
5
6
7
8

class Solution:
  def countSubsets(self, a: list[int], V: int) -> int:
    dp = [0] * (V + 1)
    dp[0] = 1
    for num in a:
      for s in range(V, num - 1, -1):
        dp[s] += dp[s - num]
    return dp[V]

Complexity

  • ⏰ Time complexity: O(n * V) — outer loop over n elements, inner loop over sums up to V.
  • 🧺 Space complexity: O(V) using the optimized 1D DP array.