Skip to content

145 — Target Sum

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

145 — Target Sum

LeetCode 494 · Medium. You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols + or - before each integer in nums and then concatenate all the integers. Return the number of different expressions that you can build which evaluates to target.

🍽️ Intuition

Picture standing in front of each number in turn, deciding whether to add it or subtract it, keeping a running total as you go. After you've made a decision for every number, you either landed exactly on target or you didn't. The running total after deciding on the first i numbers is the second dimension of state alongside "which number am I on" — describing "where am I" takes an index into nums and a running sum, which is exactly the two-index signature of 2-D DP, just with the second axis being a running total (which can go negative) instead of a plain array position.

🚩 Pattern-Recognition Cue

"Assign +/- to each number to hit a target sum, count the ways" is the subset-sum-with-signs tell: the state is (index into nums, running sum so far), a table with one axis for position and one for a value that itself needs a range of possible states — the same shape as knapsack DP, but the "capacity" axis can be negative.

🐢 Brute Force

Recurse over "index x current running sum," branching into +nums[index] and -nums[index] at every step, with no memoization.

func findTargetSumWaysBruteForce(_ nums: [Int], _ target: Int) -> Int {
    func dfs(_ index: Int, _ currentSum: Int) -> Int {
        if index == nums.count {
            return currentSum == target ? 1 : 0
        }
        return dfs(index + 1, currentSum + nums[index]) + dfs(index + 1, currentSum - nums[index])
    }

    return dfs(0, 0)
}

// smoke test
print(findTargetSumWaysBruteForce([1, 1, 1, 1, 1], 3))   // 5
print(findTargetSumWaysBruteForce([1], 1))               // 1
print(findTargetSumWaysBruteForce([1], 2))               // 0

Big-O: O(2^n) time — every number branches two ways (plus or minus), and the same (index, sum) pairs are re-explored down many different sign sequences. O(n) space for the recursion stack.

🚀 Optimal

Since every running sum is bounded by ±total (where total is the sum of all of nums), build a (n+1) x (2·total+1) table, offsetting sums by total so they can be used as non-negative array indices — dp[i][s + offset] is the number of ways to reach running sum s using the first i numbers.

func findTargetSumWays(_ nums: [Int], _ target: Int) -> Int {
    let total = nums.reduce(0, +)
    guard abs(target) <= total else { return 0 }

    let n = nums.count
    let offset = total
    let width = 2 * total + 1

    // dp[i][s + offset] = number of ways to reach running sum s using the first i numbers
    var dp = Array(repeating: Array(repeating: 0, count: width), count: n + 1)
    dp[0][offset] = 1   // zero numbers considered, running sum 0: exactly one way (do nothing)

    for i in 0..<n {
        for s in -total...total {
            let ways = dp[i][s + offset]
            guard ways != 0 else { continue }

            let plusIndex = s + nums[i] + offset
            let minusIndex = s - nums[i] + offset
            if plusIndex >= 0 && plusIndex < width {
                dp[i + 1][plusIndex] += ways
            }
            if minusIndex >= 0 && minusIndex < width {
                dp[i + 1][minusIndex] += ways
            }
        }
    }

    return dp[n][target + offset]
}

// smoke test — same cases as the brute force
print(findTargetSumWays([1, 1, 1, 1, 1], 3))   // 5
print(findTargetSumWays([1], 1))               // 1
print(findTargetSumWays([1], 2))               // 0

Big-O: O(n · total) time, where total is the sum of nums — each of n rows scans O(total) possible running sums. O(n · total) space for the dp table.

🔑 The Key Insight

Both versions make the same decision at every (index, running sum) pair — add the current number or subtract it — but the brute force treats every pair as fresh no matter how many sign sequences reach it, so the same (index, sum) combinations are re-solved exponentially many times. The optimal version fills the table row by row (one row per number considered), so row i is always finished before row i+1 needs it, and the offset trick turns "running sum can be negative" into "just another valid array index." Reusing already-solved (index, sum) states instead of re-branching from scratch is what turns exponential sign assignments into a flat O(n · total) table fill.

🔗 Related Chapters

  • 2D Dynamic Programming — a knapsack-flavored second dimension, exactly the "index x extra dimension of state" signal from chapter 27, here with the state axis being a running sum rather than remaining capacity.
  • DFS and Backtracking — the brute force is literally a DFS that branches into +/- at every number, explored fully before the optimal version memoizes the same branching into a table.
  • Arrays and Strings — the dp table is a plain 2-D array, with an offset applied to keep all indices non-negative.

🧸 Memory Sentence

Target Sum is signed subset-sum: DFS every +/- choice per number, then notice the same (index, running-sum) states recur, and tabulate them in an offset 2-D grid instead of re-branching.

✅ Check Your Understanding

  1. Why is offset = total (the sum of all of nums) guaranteed to be large enough that every possible running sum maps to a valid non-negative array index?
  2. Trace findTargetSumWays([1], 1) through the optimal version by hand. What are dp[0] and dp[1] (as sum -> count pairs), and which single index holds the final answer?
  3. The early guard abs(target) <= total else { return 0 } check isn't just an optimization — why would the code below it be unsafe (or silently wrong) without it?

⬅️ Previous: Coin Change II · Next: Interleaving String ➡️

Clone this wiki locally