Given an array of non-negative integers and a target K, return the number of subsets whose sum is exactly K. This is one of the most common subset-sum DP counting problems.
nums = array of non-negative integers, k = target sum
number of subsets with sum exactly k
Example 1:
Input:
nums = [1,2,3,3] k = 6
Output:
3
Explanation:
The subsets are [1,2,3] using the first 3, [1,2,3] using the second 3, and [3,3].
Example 2:
Input:
nums = [1,1,1,1] k = 2
Output:
6
Explanation:
Choose any 2 of the 4 ones.