Subset Sum Count

# Subset Sum Count ## Difficulty Medium ## Tags `recursion`, `dynamic programming`, `backtracking` ## Problem Statement Given a list of positive integers and a target sum, count the number of distinct subsets that sum up to exactly the target. Elements at different indices are considered distinct even if they have the same value. ## Constraints - 1 ≤ nums.length ≤ 20 - 1 ≤ nums[i] ≤ 100 - 1 ≤ target ≤ 1000 ## Signatures ### Python ```python def count_subsets(nums: List[int], target: int) -> int: pass ``` ### Java ```java public class Solution { public int count_subsets(List<Integer> nums, int target) { return null; } } ``` ### Csharp ```csharp public class Solution { public int count_subsets(IList<int> nums, int target) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int count_subsets(vector<int> nums, int target) { } }; ``` ### C ```c int count_subsets(int* nums, int target) { } ``` ### Ruby ```ruby def count_subsets(nums, target) end ``` ### Perl ```perl sub count_subsets { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def count_subsets(nums: List[Int], target: Int): Int = { } } ``` ### Haskell ```haskell count_subsets :: ... -> ... count_subsets args = undefined ``` ### Clojure ```clojure (defn count_subsets [nums target] ) ``` ### Scheme ```scheme (define (count_subsets nums target) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [10, 5, 5] target = 15 ``` **Output:** ``` 2 ``` **Explanation:** - nums[0] + nums[1] = 10 + 5 = 15 ✓ - nums[0] + nums[2] = 10 + 5 = 15 ✓ - The two 5s at different indices create two distinct subsets. ### Example 2 **Input:** ``` nums = [1, 2, 3, 4, 5] target = 5 ``` **Output:** ``` 3 ``` **Explanation:** - [5] = 5 - [1, 4] = 5 - [2, 3] = 5 ### Example 3 **Input:** ``` nums = [1, 1, 1, 1] target = 2 ``` **Output:** ``` 6 ``` **Explanation:** C(4,2) = 6 ways to pick two 1s. ## Hints 1. **Recursive approach**: For each element, choose to include or exclude it. 2. Base case: if target = 0, found a valid subset (return 1). If target < 0 or no elements left, return 0. 3. **DP approach**: Create dp[i][j] = number of ways to achieve sum j using first i elements.