Target sum
HardSigns become a subset choice
Problem
Assign + or - to each number so the expression equals a target; count the ways.
Count sign choices by tracking how many ways reach each running total.
The idea
Splitting into positive and negative groups gives P - N = target and P + N = total, so P = (total + target)/2. Counting assignments therefore reduces to counting subsets that sum to P.
The trick
- Impossible when total + target is negative or odd.
- Exactly the count-subsets recurrence once transformed.
items4
Step 1 of 6. Brute force: for each of the 4 items, branch into "skip it" or "take it". items 4.
1/6
Brute force
timeO(2ⁿ)spaceO(n)
2ⁿ decision tree.
1function go(i, sum) {2 if (i === n) return sum === target ? 1 : 0;3 return go(i + 1, sum + nums[i]) + go(i + 1, sum - nums[i]);4}Input
- nodes
- 1, 0 edges
Memory
- items
- 4
- branches
- —
- subsets
- —
Call stack
- 0visit(start)
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 1, 1, 1, 1], target = 3
- Output:
- 5
- Explanation:
- 5 ways to place + and - signs to reach 3.
Example 2
- Input:
- nums = [1], target = 1
- Output:
- 1
- Explanation:
- Just +1.
Example 3
- Input:
- nums = [1, 2, 1], target = 0
- Output:
- 2
- Explanation:
- +1-2+1 and -1+2-1 both hit 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.