Count the number of ways to assign + and - signs to reach a target sum.
You are given an array of integers nums and an integer target.
For every number in nums, choose either a + sign or a - sign and form an expression. Your task is to count how many different sign assignments produce a total sum equal to target.
Two assignments are considered different if at least one number receives a different sign.
This is a counting problem: do not return one valid expression, return the total number of valid assignments.
Input Format
nums: an array of integerstarget: an integer
Return the number of sign assignments whose total sum equals target.
Output Format
- Return an integer representing the count of valid assignments.
Constraints
- The input array may contain zeros.
- The answer fits within a 32-bit signed integer in the standard problem setting.
- A brute-force search over all sign assignments may be too slow for larger inputs.
Example 1
Input
nums = [1,1,1,1,1], target = 3
Output
5
Explanation
There are 5 ways to assign signs so the expression evaluates to 3.
Example 2
Input
nums = [1], target = 1
Output
1
Explanation
Only +1 works.
Show 1 more example
Example 3
Input
nums = [1,0], target = 1
Output
2
Explanation
The 0 can be assigned either + or - without changing the sum, so there are 2 valid assignments.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.