Placing Plus and Minus Signs

Medium

You get an array of non-negative integers values and an integer goal. Put a + or a - in front of every number, then add up the resulting terms. How many sign assignments make the total equal goal? Two assignments differ if at least one element gets a different sign, even when that element is zero.

Example 1

values=[2, 3, 5], goal=0 → 2

Both +2 +3 -5 and -2 -3 +5 work.

Example 2

values=[4, 0, 1], goal=3 → 2

We need +4 -1; the zero can take either sign, so there are two ways.

Example 3

values=[6], goal=4 → 0

Constraints

1 ≤ len(values) ≤ 20
0 ≤ values[i] ≤ 1000
sum(values) ≤ 1000
-1000 ≤ goal ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Backtracking

Similar problems

Square Frame From Sticks Medium Seating by Divisibility Medium Cheapest Basket with Bundles Medium Groups With Equal Sums Medium Least Total Walk to Scooters Medium

Input

values=[2, 3, 5], goal=0

Expected

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.