Skip to main content

494. Target Sum

medium

Assign + or - to every number to reach a target sum. Count the number of expressions. Algebraically reduces to subset-sum on a derived target.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 and then concatenate all the integers. For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression '+2-1'. Return the number of different expressions that you can build, which evaluates to target.

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

Examples

Example 1

Input
nums = [1,1,1,1,1], target = 3
Output
5

Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3. +1 - 1 + 1 + 1 + 1 = 3. +1 + 1 - 1 + 1 + 1 = 3. +1 + 1 + 1 - 1 + 1 = 3. +1 + 1 + 1 + 1 - 1 = 3.

Example 2

Input
nums = [1], target = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Let P be the sum of the positive subset and N the sum of the negative subset. P + N = total and P - N = target.

Hint 2

Adding the equations: P = (total + target) / 2. The problem reduces to counting subsets that sum to P.

Hint 3

Subset-count DP: dp[s] is the number of subsets summing to s. Initialize dp[0] = 1; for each num, sweep s from P down to num and dp[s] += dp[s - num].

Solution approach

Reveal approach

Let P be the absolute sum of numbers assigned a '+' and N the absolute sum of those assigned '-'. Then P + N = total and P - N = target, so P = (total + target) / 2. If total + target is negative or odd, return 0. The problem becomes: how many subsets of nums sum to P? Use 1D count DP: dp[s] starts as dp[0] = 1; for each num, sweep s from P down to num and increment dp[s] += dp[s - num]. The reverse order enforces 0/1 use of each num. Return dp[P]. O(n * P) time, O(P) space. Handle target out of range early by returning 0.

Complexity

Time
O(n * (sum + target))
Space
O(sum + target)

Related patterns

  • dynamic-programming
  • knapsack-0-1

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Facebook
  • Google

Practice these live with InterviewChamp.AI

Drill Target Sum and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →