Count Subsets With Sum

Count the ways to choose exactly k positions from nums so that the chosen values add up to target. Two choices are different if they use different positions, even when the values are equal.

Choosing zero items (k = 0) gives exactly one way, with sum 0.

Examples

Example 1

Input:

count_subset_sums([1, 2, 3, 4], 2, 5)

Output:

2

The positions with values (1, 4) and (2, 3).

Example 2

Input:

count_subset_sums([2, 2, 2], 2, 4)

Output:

3

Every pair of positions works: 3 ways.

Constraints

• 0 <= len(nums) <= 22
• 0 <= k <= len(nums)
• -100 <= nums[i] <= 100
• -2200 <= target <= 2200