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 Sam K., 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

More DP 1D practice problems

See all DP 1D problems →