Target Sum

Problem

Count the number of ways to assign a plus or minus sign to every element of nums so the resulting expression equals target.

Use a dictionary DP mapping each reachable sum to its number of assignments, expanding both signs for every element. Return 1 when nums is empty and target is 0.

Hint

Each element doubles the number of reachable sums, so merge counts per sum in a dictionary.

Test cases

case 1

in: [[1,1,1,1],1]

expected: 0

case 2

in: [[1,2,3],4]

expected: 1

case 3

in: [[0],0]

expected: 2

case 4

in: [[1],2]

expected: 0

case 5

in: [[],0]

expected: 1

Starter codePython

def target_sum(nums, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor