Target Sum

The key idea

Split nums into a positive group P (gets +) and a negative group N (gets -). Then sum(P) - sum(N) = target and sum(P) + sum(N) = total. Adding the two gives sum(P) = (target + total) / 2. So the answer is just the number of subsets of nums whose sum equals that fixed value S — a classic 0/1-knapsack subset-count. If target + total is odd or negative, the answer is 0.

Problem

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols + and - before each integer in nums, and then concatenate all the integers.

Return the number of different expressions that you can build, which evaluates to target. Each number in nums must receive exactly one symbol, and all numbers must be used.

Constraints

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Examples

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

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

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

Complexity

Time: O(n * P) Space: O(P)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →