Target Sum
The briefingthe full drill, in my own words
The drill: Each number in the array gets a + or − sign written in front of it. Count how many different sign assignments make the resulting expression evaluate to the target.
An array of non-negative numbers and a target arrive together. The task is to place either a plus sign or a minus sign in front of every single number, then count how many of those sign assignments make the resulting sum equal the target exactly.
Every number in the array gets exactly one sign — none are skipped and none get both. Two assignments count as different the moment any single number's sign differs between them, even if the totals happen to coincide along the way.
The output is just that count of valid sign assignments, which can be zero if no combination of signs ever lands on the target.
- array values are non-negative integers
- every number gets exactly one of + or -, no skipping
- arrays stay small enough for a sum-indexed DP table
- the count can be zero when no sign assignment reaches the target
The hintstake only what you need
HINT 1 THE NUDGE
Trying every ± assignment is 2^n work, but many assignments end up re-deriving the exact same running total. What repeats across branches?
HINT 2 THE STRUCTURE
Split the numbers into a 'plus' group P and a 'minus' group N. Their difference must equal target, and P + N is always the fixed total of all numbers — so P's required sum is forced the moment you know the total and target.
HINT 3 ONE STEP FROM THE ANSWER
Solve P = (total + target) / 2, then count subsets of nums that sum to exactly P with a reachability-count DP over achievable sums. If P isn't a whole number in range, the answer is zero.
Coach's boardthe pattern, step by step
nums=[1,2,3], target=2. total=6, so S=(6+2)/2=4 — count subsets summing to 4; that count is the answer. dp[0]=1.
The splitstwo paces, two languages
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
total = sum(nums)
if abs(target) > total or (total + target) % 2 != 0:
return 0
s = (total + target) // 2
dp = [0] * (s + 1)
dp[0] = 1
for x in nums:
for a in range(s, x - 1, -1):
dp[a] += dp[a - x]
return dp[s]class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
def dfs(i, total):
if i == n:
return 1 if total == target else 0
return dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i])
return dfs(0, 0)class Solution {
public int findTargetSumWays(int[] nums, int target) {
int total = 0;
for (int x : nums) {
total += x;
}
if (Math.abs(target) > total || (total + target) % 2 != 0) {
return 0;
}
int s = (total + target) / 2;
int[] dp = new int[s + 1];
dp[0] = 1;
for (int x : nums) {
for (int a = s; a >= x; a--) {
dp[a] += dp[a - x];
}
}
return dp[s];
}
}class Solution {
private int[] nums;
private int target;
private int n;
public int findTargetSumWays(int[] nums, int target) {
this.nums = nums;
this.target = target;
n = nums.length;
return dfs(0, 0);
}
private int dfs(int i, int total) {
if (i == n) {
return total == target ? 1 : 0;
}
return dfs(i + 1, total + nums[i]) + dfs(i + 1, total - nums[i]);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED