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.
nums = [2, 1]
, you can add a '+'
before 2
and a '-'
before 1
and concatenate them to build the expression "+2-1"
.Return the number of different expressions that you can build, which evaluates to target
.
Example 1:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1 Output: 1
Constraints:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
This problem asks to find the number of ways to assign either '+' or '-' to each element in a given integer array nums
such that the resulting sum equals a given target
.
Core Idea: The problem can be elegantly reframed using a simple algebraic manipulation. Let's say S
is the sum of all elements in nums
. If we assign '+' to some elements and '-' to others, the resulting sum can be expressed as:
(Sum of elements with '+') - (Sum of elements with '-') = target
Let P
represent the sum of elements with '+' and N
represent the sum of elements with '-'. Then:
P - N = target
We also know that:
P + N = S
(the sum of all elements)
Adding the two equations gives:
2P = target + S
P = (target + S) / 2
This implies that if target + S
is odd or S < target
, there's no solution (we can't have a fractional number of elements). If a solution exists, it boils down to finding the number of ways to select elements from nums
that sum up to P
.
This subproblem is a classic combinatorial problem that can be solved efficiently using dynamic programming.
This approach uses a 2D array dp
where dp[i][j]
represents the number of ways to obtain a sum j
using the first i
elements of nums
.
State Transition: For each element nums[i]
, we have two choices: include it (adding its value) or exclude it. Thus:
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]]
(if j >= nums[i]
)
The base case is dp[0][0] = 1
(there's one way to get a sum of 0 using no elements).
Time Complexity: O(len(nums) * sum(nums)) - because the dp table has dimensions proportional to the length of the input array and the sum of its elements.
Space Complexity: O(len(nums) * sum(nums)) - for the 2D dp array.
We can optimize space by observing that each row in the dp
table only depends on the previous row. Hence, we can reduce the dp array to a 1D array, iterating backwards to avoid overwriting values needed in the current iteration.
Time Complexity: O(len(nums) * sum(nums)) - remains the same as the algorithm still iterates through all the combinations.
Space Complexity: O(sum(nums)) - significantly reduced to a single 1D array.
Solution 1 (2D DP):
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (s - target) % 2 != 0 or s < target:
return 0
p = (s + target) // 2
n = len(nums)
dp = [[0] * (p + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(p + 1):
dp[i][j] = dp[i - 1][j]
if j >= nums[i - 1]:
dp[i][j] += dp[i - 1][j - nums[i - 1]]
return dp[n][p]
Solution 2 (1D DP):
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
s = sum(nums)
if (s - target) % 2 != 0 or s < target:
return 0
p = (s + target) // 2
dp = [0] * (p + 1)
dp[0] = 1
for num in nums:
for j in range(p, num - 1, -1):
dp[j] += dp[j - num]
return dp[p]
Both solutions achieve the same result, but the second one is more memory-efficient. The code in other languages would follow similar logic, adapting the syntax accordingly.