Skip to content
Onsite
34 / 48

Target Sum

MediumP2Coding

Put a + or a - in front of every number in nums and add them all up. Return the number of different sign assignments whose total equals target.

Signs are assigned by position, so equal numbers at different positions give different assignments. A 0 can take either sign, which counts as two assignments.

Example 1

Input
nums = [1,1,1,1,1], target = 3
Output
5
Why
Five assignments: any one of the five 1s takes the minus sign.

Example 2

Input
nums = [1], target = 1
Output
1

Example 3

Input
nums = [1], target = 2
Output
0

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums) <= 1000
  • -1000 <= target <= 1000

Hints

Run checks the 3 visible tests, Submit all 12.