Count of Subset Sum

Explore how to count the number of subsets within a set that sum to a given target by applying dynamic programming methods. Understand both naive recursive and optimized top-down and bottom-up approaches to efficiently solve the subset sum problem with clear examples and code implementations.

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