You are given an integer array nums and an integer target. Put either a + or a - sign in front of every number and then add them all up. Return the number of different sign assignments whose result equals target.
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums) <= 1000
- -1000 <= target <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force tries both signs for every number: 2^n combinations, fine for n = 20 but it does not scale. A memo on (index, running sum) cuts it to O(n * total). The neat insight is algebra: the plus group sums to P and the minus group to N, with P - N = target and P + N = total, so P = (total + target) / 2. Now the task is count subsets with sum `P`. State: dp[s] = number of subsets of the numbers seen so far summing to s. Recurrence: for each x, dp[s] += dp[s - x], iterating s downwards so each number is used once. Base case: dp[0] = 1 (the empty subset).
Algorithm
- Compute
total. Ifabs(target) > totalor(total + target)is odd, return 0. - Let
P = (total + target) / 2and createdpof sizeP + 1withdp[0] = 1. - For each
xinnums, forsfromPdown tox, adddp[s - x]todp[s]. - Return
dp[P].
O(n * total)Space: O(total)x = 0 the update dp[s] += dp[s] doubles every entry. Try [0,0,0], target = 0, which has 8 ways.class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: total = sum(nums) if abs(target) > total or (total + target) % 2: return 0 P = (total + target) // 2 # sum of the plus group dp = [0] * (P + 1) # dp[s] = number of subsets with sum s dp[0] = 1 for x in nums: for s in range(P, x - 1, -1): # backwards: each number once dp[s] += dp[s - x] return dp[P]