Dynamic Programming
LC #494Medium
Target Sum
Dynamic Programming
AmazonGoogleMetaProblem
Assign + or - to each number to reach a target sum. Count the number of ways.
arraydynamic-programmingbacktracking
Constraints
- ›1 ≤ nums.length ≤ 20
- ›0 ≤ nums[i] ≤ 1000
- ›0 ≤ sum(nums[i]) ≤ 1000
- ›-1000 ≤ target ≤ 1000
Example
Input
nums = [1, 1, 1, 1, 1], target = 3Output
5Why
-1+1+1+1+1, 1-1+1+1+1, 1+1-1+1+1, 1+1+1-1+1, 1+1+1+1-1 = 5 ways