163. Target Sum

Medium · Dynamic Programming

You are given an array of numbers and a target sum. Your task is to assign either a plus (+) or minus (−) sign to each number, then count how many different ways you can do this so that the signed sum equals the target.

For example, with [1,1,1,1,1] and target 3, you could assign signs like +1+1+1+1−1 = 3. Count all such valid assignments.

Input: an array `nums` of positive integers and an integer `target`. Return the total number of ways to assign signs to reach the target sum.

Examples

Example 1
Input: [[1,1,1,1,1], 3]
Output: 5
Explanation: Five sign assignments produce sum 3

Example 2
Input: [[1], 1]
Output: 1
Explanation: Only +1 works

Constraints

• Standard input/output constraints apply