Skip to content
BASA DSA

Target Sum

Medium2-D Dynamic Programming

Assign + or - to each array entry and sum the signed entries. Return the number of index-wise sign assignments producing target; zero entries still have two sign choices.

Example 1

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

Explanation

Exactly one of three 1 entries must be negative, giving three assignments.

Example 2

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

Explanation

Each zero independently takes either sign, giving four assignments while 1 is positive.

Example 3

Input
nums = [2]
target = 1
Output
0

Explanation

The only sums are 2 and -2, neither matching 1.

Constraints

  • 1 <= len(nums) <= 20
  • Values are nonnegative
  • Sum of values <= 1000
  • abs(target) <= 1000

Function contractfindTargetSumWaysArguments: json, json
Loading draft…
SolutionRuns on your device