Asked at

Target Sum

Medium
VerifiedArrayDynamic ProgrammingKnapsack~25 min

Assign + or - to each number in nums, then sum them. Count the assignments that produce target.

The input arrives as a single object { nums, target }. Return the count.

Examples

in{ nums: [1, 1, 1, 1, 1], target: 3 }
out5

Five sign assignments reach 3, e.g. -1+1+1+1+1.

in{ nums: [1], target: 1 }
out1

Only +1 works.

Constraints

  • 1 ≤ nums.length ≤ 20
  • 0 ≤ nums[i] ≤ 1000
  • -1000 ≤ target ≤ 1000
  • Target: O(n · sum) time

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.