loading

Target Sum — Step-by-Step Visualization

mediumLeetCode #494ArrayDynamic ProgrammingBacktracking

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 `+` and `-` before each integer in `nums`. Return the number of different expressions that you can build which evaluates to `target`.

Algorithm Pattern

Dynamic Programming (Running Sum Map)

Key Idea

Track a map from running sum → number of ways to reach that sum. For each number, expand each existing sum by both +n and -n. The answer is dp[target] after processing all numbers.

Step-by-Step Approach

  1. dp = {0: 1} (one way to reach sum 0 with empty prefix).
  2. For each n: new_dp[s + n] += dp[s], new_dp[s - n] += dp[s].
  3. Replace dp = new_dp.
  4. Return dp.get(target, 0).

Common Gotchas

  • Must use new_dp per iteration — don't update dp in place.
  • The same running sum can be reached by multiple expressions — values in dp are counts.

Related Problems

← All problems