Put + or − before every number and count the ways to hit the target. The sign tree doubles at every step, but the same (index, running total) keeps coming back, so memoize it and the work drops to O(n·S).
▼The problem
LeetCode 494 (Medium). Given an integer array nums and an integer target, put a + or a - in front of every number and count the expressions that evaluate to target.
Examples (LeetCode's): nums = [1,1,1,1,1], target = 3 → 5 (the walkthrough example: four pluses and one minus, and any of the five ones can be the minus); nums = [1], target = 1 → 1 (scene 1: +1 hits, -1 misses).
The solution
from functools import cache
def findTargetSumWays(nums, target):
@cache
def dfs(i, total):
if i == len(nums):
return 1 if total == target else 0
return (dfs(i + 1, total + nums[i]) +
dfs(i + 1, total - nums[i]))
return dfs(0, 0)Transcript
Target Sum. Put a plus or a minus in front of every number, and count how many of those expressions add up to the target.
Take five ones and a target of three. Four pluses and one minus make three, and any of the five ones can be the minus, so the answer is five.
The naive way is backtracking: at every number, branch on plus or minus. That's a tree with two to the n leaves: thirty-two here, over a million for twenty numbers.
But plus one, minus one lands on the same sum as minus one, plus one. A state is just the index and the running total, and the same states keep coming back. So memoize: solve each state once, and reuse its count.
In code, a cached helper takes the index and the total. Past the last number, it returns one if the total hits the target. Otherwise, it adds the counts for plus and minus.
Let's walk it. After three numbers, a total of one is reached three ways, but solved once. Sixty-three calls shrink to twenty-one states. Counts flow back up: each state adds its two children, and the root gets four plus one. Five.
There's a shortcut too. The plus group must sum to the total plus the target, over two: four here. So count the subsets that sum to four, with a one-row table. Five again.
The cache holds n times sum states, order n times sum time and space. The table needs only order sum space.
Branch, cache, reuse. That's Target Sum.