Plus or Minus to Target
EasyBacktracking
Problem
You are given an array nums and an integer target. Put either + or - in front of every number and add them all up.
Return how many of the 2^n sign assignments make the total equal target.
Example 1
- Input:
- nums = [1, 1, 1, 1, 1], target = 3
- Output:
- 5
Exactly one of the five 1s must be negative: five choices.
Example 2
- Input:
- nums = [2], target = 2
- Output:
- 1
Constraints
- 1 ≤ nums.length ≤ 18
- 0 ≤ nums[i] ≤ 1000
- -1000 ≤ target ≤ 1000
Hint
Show the first hint
Each number has exactly two choices. What does the full decision tree look like?
Walkthrough
How to approach it
01Clarify before coding
- Must every number get a sign? Yes, none can be skipped.
- Does a 0 count twice? Yes: +0 and -0 are different assignments with the same total.
- How large is n? 18, so 2^18 = 262,144 leaves is acceptable.
02Brute force
Loop over all 2^n bitmasks, compute each signed sum from scratch.
Cost: O(n · 2^n): recomputing every sum from the start repeats work shared by assignments with the same prefix.
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.