LeetCode 494 · Medium · 2-D Dynamic Programming

Target Sum

Put a + or a − in front of every number in nums. Count how many of those sign choices make the whole expression equal target.

O(n·S)time · S = sum of nums
O(n·S)space
memo DFSon (index, total)

nums: 1–6 values, 0 to 5 each, adding up to at most 5 · target: −9 to 9

dp row i = numbers already signed · column = running total · cell = ways to reach target from there

Call stack bottom → top

Map<String, Integer> dp = new HashMap<>(); // "i,total" -> waysint[] nums;int target;public int findTargetSumWays(int[] nums, int target) { this.nums = nums; this.target = target; return backtrack(0, 0);}private int backtrack(int i, int total) { if (i == nums.length) { return total == target ? 1 : 0; } String key = i + "," + total; if (dp.containsKey(key)) { return dp.get(key); } int ways = backtrack(i + 1, total + nums[i]) + backtrack(i + 1, total - nums[i]); dp.put(key, ways); return ways;}
i, total
—
nums[i]
—
memo entries
0
memo hits
0

Why it works

  1. Brute force tries every sign pattern: 2n of them, each summed in O(n).
  2. The future only depends on (i, total). However you signed the first i numbers, if they add up to the same total, the ways to finish are the same. So each pair is solved once and cached, and later calls are memo hits.
  3. Complexity: i takes n+1 values and total stays within ±S, so there are at most (n+1)·(2S+1) states, each doing O(1) work: O(n·S) time and space.
  4. Pitfall: totals go negative, so an array index needs an offset of S; a HashMap keyed by "i,total" avoids that. And zeros double the count: +0 and −0 are different sign choices.
  5. Follow-up: if P is the sum of the plus group, then P − (S − P) = target, so P = (S + target) / 2. The problem becomes "count subsets that add up to P", a 1-D 0/1 knapsack in O(n·S) time and O(S) space.