Target Sum
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Put + or - in front of each number so the total equals target. Count the ways.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If P is the sum of the + numbers, write P - (total - P) = target and solve for P.
- Hint 2When is the answer impossible regardless of counting?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Splitting a list of expenses between Team A and Team B so that A's total minus B's total is exactly the target. Since A + B is the grand total, A's total is forced: (grand total + target) / 2. So the question is only: in how many ways can Team A's expenses add up to that number? Count with a ways-chart over totals, using each expense once.
- The obvious way
Try all 2^n sign choices: O(2^n).
- The key insight
If |target| > total or (total + target) is odd, return 0. Otherwise need = (total + target) / 2. ways[0] = 1; for each number, go from need down to the number: ways[sum] += ways[sum - number]. Answer ways[need].
- The algorithm
- Check feasibility; need = (total + target) / 2.
- ways[0] = 1.
- For each number, loop sums from need down to number: add ways[sum - number].
- Return ways[need].
Watch it run
Examplenums = [1, 1, 1, 1, 1], target = 3
Total is 5. Team A's total must be (5 + 3) / 2 = 4.
need = 4
Where people slip
- Zeros in the input double the count, which the downward loop with number = 0 handles correctly.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_target_sum_ways(nums, target):
total = sum(nums)
if abs(target) > total or (total + target) % 2 == 1:
return 0 # Team A's total cannot be a whole number
need = (total + target) // 2 # Team A's total
ways = [0] * (need + 1)
ways[0] = 1 # one way to make 0: take nothing
for number in nums:
for made in range(need, number - 1, -1): # downwards: each expense is used once
ways[made] += ways[made - number]
return ways[need]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.