Signs that reach a target
Medium · Target 20 minutes · Backtracking· Type asked at
Amazon
Citadel
IMC
Given an array of non-negative integers nums and an integer target,
put a + or a − in front of every number and add them up. Return the number of
sign choices whose total equals target.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 1, 1, 1, 1], target = 3 | 5 | Exactly one of the five 1s gets a minus sign. |
nums = [2, 3, 5], target = 0 | 2 | 2 + 3 − 5 and −2 − 3 + 5. |
nums = [0, 0, 1], target = 1 | 4 | A zero can take either sign, so each zero doubles the count. |
Constraints
- 1 ≤ n ≤ 20
- 0 ≤ nums[i] ≤ 1000
- 0 ≤ target ≤ 1000
Hints
Hint 1
Each number has two choices, so there are 2ⁿ sign patterns. With n ≤ 20 that is about a million: can you walk them all?
Hint 2
Recurse on the index, carrying the running total. At the end, count 1 if the total equals the target.
Hint 3
The same (index, running total) pair is reached by many different paths. Memoise on it, and the search becomes dynamic programming.
Where people lose marks
- Skipping zeros or treating +0 and −0 as one choice. They are different sign choices, so each zero doubles the count.
- Memoising on the index alone. The number of ways depends on the running total too.
- In the subset-sum form, forgetting the parity check: (total + target) must be even, or there are no solutions.
- Allowing target larger than the total: no sign pattern can reach it, and a memo table indexed by total + target would overflow its bounds.
Dry run on [2,3,5],0
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums+20+31+52total10found0
+2 +3 +5 = 10. Not 0.
-
Step 2 / 8nums+20+31−52total0found1
+2 +3 −5 = 0. That hits 0: count it (1 so far).
-
Step 3 / 8nums+20−31+52total4found1
+2 −3 +5 = 4. Not 0.
-
Step 4 / 8nums+20−31−52total-6found1
+2 −3 −5 = -6. Not 0.
-
Step 5 / 8nums−20+31+52total6found1
−2 +3 +5 = 6. Not 0.
-
Step 6 / 8nums−20+31−52total-4found1
−2 +3 −5 = -4. Not 0.
-
Step 7 / 8nums−20−31+52total0found2
−2 −3 +5 = 0. That hits 0: count it (2 so far).
-
Step 8 / 8nums−20−31−52total-10found2
−2 −3 −5 = -10. Not 0. All 8 sign patterns checked: 2 ways.
How to think about it
Every number gets one of two signs, so the choices form a binary tree of depth n. The direct search walks it, carrying the running total:
- At index i, recurse twice: with
total + nums[i]and withtotal − nums[i]. - At index n, return 1 if the total equals the target, otherwise 0.
That is O(2ⁿ): about a million leaves for n = 20, fine. But many paths reach the same (index, running total) pair, and the number of ways to finish from there does not depend on how you arrived. Memoising on that pair cuts the work to O(n × S), where S is the range of possible totals (−sum to +sum).
There is a sharper reformulation. Let P be the numbers given a plus sign and N the rest. Then
P − N = target and P + N = total, so P = (total + target) / 2.
The question becomes: how many subsets sum to that value? If total + target is odd, or target exceeds
total, the answer is 0 immediately.
The progression, search then memoise then reformulate, is what interviewers want to watch. Say each step out loud, with its complexity, before you write the next.
Complexity. Time O(2ⁿ); O(n × sum) memoised · Space O(n); O(n × sum) memoised
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
from functools import lru_cache
def target_sum_signs(nums, target):
@lru_cache(maxsize=None)
def ways(i, total): # sign choices for nums[i:] that finish at target
if i == len(nums):
return 1 if total == target else 0
return ways(i + 1, total + nums[i]) + ways(i + 1, total - nums[i])
return ways(0, 0)#include <vector>
#include <numeric>
// Subset-sum form: count subsets summing to (total + target) / 2.
long long solve(const std::vector<int>& nums, int target) {
long long total = std::accumulate(nums.begin(), nums.end(), 0LL);
if (target > total || (total + target) % 2 != 0) return 0;
const int want = static_cast<int>((total + target) / 2);
std::vector<long long> ways(want + 1, 0);
ways[0] = 1;
for (int x : nums)
for (int s = want; s >= x; --s) // descending, so each number is used at most once
ways[s] += ways[s - x];
return ways[want];
}class Solution {
// Subset-sum form: count subsets summing to (total + target) / 2.
public long targetSumSigns(int[] nums, int target) {
long total = 0;
for (int x : nums) total += x;
if (target > total || (total + target) % 2 != 0) return 0;
int want = (int) ((total + target) / 2);
long[] ways = new long[want + 1];
ways[0] = 1;
for (int x : nums)
for (int s = want; s >= x; s--) // descending: each number used at most once
ways[s] += ways[s - x];
return ways[want];
}
}function targetSumSigns(nums, target) {
const memo = new Map(); // "i,total" -> number of ways to finish
const ways = (i, total) => {
if (i === nums.length) return total === target ? 1 : 0;
const key = i + ',' + total;
if (memo.has(key)) return memo.get(key);
const r = ways(i + 1, total + nums[i]) + ways(i + 1, total - nums[i]);
memo.set(key, r);
return r;
};
return ways(0, 0);
}// The plain search: 2^n leaves, fine for n <= 20.
fn walk(nums: &[i64], i: usize, total: i64, target: i64) -> i64 {
if i == nums.len() {
return if total == target { 1 } else { 0 };
}
walk(nums, i + 1, total + nums[i], target) + walk(nums, i + 1, total - nums[i], target)
}
fn solve(nums: &[i64], target: i64) -> i64 {
walk(nums, 0, 0, target)
}-- The plain search: each number is added or subtracted; count leaves at the target.
solve :: [Int] -> Int -> Int
solve nums target = go nums 0
where
go [] total = if total == target then 1 else 0
go (x : xs) total = go xs (total + x) + go xs (total - x)Variants to try
- Return one sign pattern that works rather than the count: the same search, stopping at the first success.
- n up to 200 with small values: only the subset-sum DP is fast enough, in O(n × sum) with a one-dimensional table.
- Negative numbers allowed: the sign of each number flips its contribution anyway, so replace each with its absolute value.
Next problems
Sum of every subset’s XOR
Every element is either in or out. Walking that binary tree visits each subset once, carrying its XOR as you go.
Open the problem → Hard25 minCounting n-queens placements
Place one queen per row, and never place one where it is already attacked. Bitmasks make the check a single AND.
Open the problem →Write a solution and run it against the real test table.
Keep going
Sum of every subset’s XOR
Every element is either in or out. Walking that binary tree visits each subset once, carrying its XOR as you go.
Open the problem → Hard25 minCounting n-queens placements
Place one queen per row, and never place one where it is already attacked. Bitmasks make the check a single AND.
Open the problem → BacktrackingThe pattern behind it
Build a solution one choice at a time, and abandon a branch the moment it cannot succeed.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.