Plus-Minus Ledger
Medium2-D Dynamic Programming
Problem
An auditor has a list of non-negative amounts nums whose signs were lost. Each amount was either a credit (+) or a debit (-), and the ledger balanced to target.
Count how many ways to put a + or - in front of every amount make the signed sum equal target. Two ways differ if some position has a different sign, even when the amounts are equal.
Example 1
- Input:
- nums = [1, 2, 1, 2], target = 2
- Output:
- 3
+1 +2 +1 -2, +1 -2 +1 +2 and -1 +2 +1 +2 all sum to 2.
Example 2
- Input:
- nums = [4, 1], target = 0
- Output:
- 0
Example 3
- Input:
- nums = [0, 0, 3], target = 3
- Output:
- 4
Each 0 can take either sign, so the single way to get 3 from [3] is multiplied by 2 · 2.
Constraints
- 1 ≤ nums.length ≤ 20
- 0 ≤ nums[i] ≤ 1000
- 0 ≤ sum(nums) ≤ 1000
- -1000 ≤ target ≤ 1000
Hint
Show the first hint
Split the amounts into the ones that got + (set P) and the ones that got - (set N). Write two equations about their sums.
Walkthrough
How to approach it
01Clarify before coding
- Does every amount have to be used? Yes, each gets a sign.
- Do zeros count twice? Yes: +0 and -0 are different sign choices, so they double the count.
- Can target be negative or out of reach? Yes to both; out of reach means 0 ways.
02Brute force
Enumerate all 2^n sign patterns and count the ones that hit target.
Cost: O(2^n · n): about 2 · 10^7 operations for n = 20. It passes here, but it does not scale and an interviewer expects the DP.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.