Count Subsets with Sum K
Problem statement
You are given an integer array nums and an integer k. Return the number of subsets of nums whose elements add up to exactly k.
A subset is chosen by positions, so equal values at different indices are different choices. The empty subset has sum 0, so it is counted when k is 0.
Function
countSubsetsWithSum(nums: int[], k: int) → longExamples
Example 1
nums = [1,2,3,3]k = 6return = 3There are two 3s, at indices 2 and 3. The subsets with sum 6 are 1 + 2 + 3 using the first 3, 1 + 2 + 3 using the second 3, and 3 + 3. That makes 3 subsets.
Example 2
nums = [2,0,2]k = 2return = 4Each 2 alone has sum 2. Adding the 0 to either one keeps the sum at 2, which gives two more subsets. The answer is 4.
Example 3
nums = [5,10]k = 0return = 1Every element is positive, so only the empty subset has sum 0. The answer is 1.
Constraints
1 <= nums.length <= 300 <= nums[i] <= 10000 <= k <= 30000