Count of Subset Sum

Explore how to count the number of subsets from a set that sum up to a target value using dynamic programming. Learn to optimize naive recursive methods with top-down memoization and bottom-up tabulation approaches in the 0/1 Knapsack context, improving time and space efficiency.

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 targetSum, count the total number of subsets of the given set whose sum is equal to the targetSum.

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$ targetSum $\leq 10^5$
$0\leq$ nums[i] $\leq 10^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