All problems

Target Sum

Medium · dynamic programming

You are given a list of non-negative integers nums and an integer target.

Put either a + or a - sign in front of every number, then add them all up. Return the number of different ways to choose the signs so that the total equals target.

Two ways are different if some position gets a different sign. A 0 can take either sign, so it doubles the count. If no choice of signs works, return 0.

Examples

Example 1

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

Output: 5

Exactly one of the five 1s takes a minus sign, and there are 5 choices for which one: 4 - 1 = 3.

Example 2

Input: nums = [2, 3], target = 0

Output: 0

The four totals are 5, -1, 1 and -5, and none is 0.

Example 3

Input: nums = [0, 0], target = 0

Output: 4

Each 0 can be +0 or -0 and every combination totals 0.

Constraints