Count of Subset Sum

Explore how to count the total number of subsets from a given set that sum exactly to a target value. Understand the naive recursive approach and then master the optimization using dynamic programming with both top-down memoization and bottom-up tabulation methods. Learn to improve time complexity from exponential to polynomial and effectively manage space using 2D lookup tables.

We'll cover the following...

Statement
Examples
Try it yourself
Solution
- Naive approach
  - Time complexity
  - Space complexity
- Optimized solution using dynamic programming
  - Top-down solution
    - Time complexity
    - Space complexity
  - Bottom-up solution
    - Time complexity
    - Space complexity

Statement

Given a set of positive numbers nums and a value target_sum, count the total number of subsets of the given set whose sum is equal to the target_sum.

Let’s say you are given a set = $\{$ $1, 2, 3, 4$ $\}$ and a target sum = $4$ . The output will be 2 as the following subsets:

$\{$ $1, 3$ $\}$
$\{$ 4 $\}$

will add up to make the desired sum.

Constraints:

$1\leq$ nums.length $\leq 1000$
$0\leq$ target_sum $\leq 25 *10^4$
$1\leq$ nums[i] $\leq 1 0^{4}$

...

1.Getting Started

2.0/1 Knapsack

3.Unbounded Knapsack

4.Recursive Numbers

5.Longest Common Substring

6.Palindromic Subsequence

7.Conclusion

Count of Subset Sum

Statement