Subset Sum Count
MediumDynamic ProgrammingArrayMathBacktracking
Description
Given an array of non-negative integers and a non-negative target, return the number of (index-distinct) subsets whose sum equals target. The empty subset has sum 0 and counts.
Examples
Input:
nums = [1,2,3], target = 3Output:
2Explanation:
Two subsets of [1,2,3] sum to 3: {3} and {1,2}.
Input:
nums = [1,1,1], target = 2Output:
3Explanation:
Three index-distinct ways to pick two of the three 1s give sum 2: {0,1}, {0,2}, {1,2}.
Input:
nums = [5], target = 0Output:
1Explanation:
Only the empty subset of [5] sums to 0, giving exactly one way.
Constraints
- •
1 ≤ nums.length ≤ 30 - •
0 ≤ nums[i] ≤ 100 - •
0 ≤ target ≤ 1000