Scale Engineer

Target Sum

Med
#0481Time: O(2^n), where `n` is the length of the `nums` array. At each step, the function branches into two recursive calls, leading to a recursion tree with `2^n` leaf nodes.Space: O(n), where `n` is the length of the `nums` array. This space is used by the recursion call stack, which can go as deep as `n`.3 companies
Patterns
Dynamic ProgrammingBacktracking
Data structures
Array
Companies
MyntraServiceNowPinterest

Prompt

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.

 

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

 

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses recursion to explore every possible combination of + and - signs for the numbers in the input array. It constructs a binary decision tree where, at each level corresponding to an element in nums, it branches into two possibilities: adding the element or subtracting it. The total count is the number of paths in this tree that result in the target sum.

Algorithm

  • Define a recursive function, say calculate(nums, index, currentSum, target).
  • The base case for the recursion is when index reaches the end of the nums array (index == nums.length).
    • If currentSum is equal to target, it means we have found a valid expression. Return 1.
    • Otherwise, return 0.
  • In the recursive step, for the number at nums[index], we explore both possibilities:
    1. Adding the number: Make a recursive call calculate(nums, index + 1, currentSum + nums[index], target).
    2. Subtracting the number: Make a recursive call calculate(nums, index + 1, currentSum - nums[index], target).
  • The total number of ways is the sum of the results from these two recursive calls.
  • The initial call to start the process is calculate(nums, 0, 0, target).

Walkthrough

The core idea is to build a recursive function that traverses through the nums array. This function keeps track of the current index being processed and the sum accumulated so far. For each number, the function calls itself twice: once for the case where the number is added to the sum, and once for the case where it's subtracted. The recursion stops when all numbers have been processed. At this point, if the accumulated sum equals the target, we have found one valid expression. The final result is the total count of all such valid expressions found across all recursive paths.

class Solution {    int count = 0;    public int findTargetSumWays(int[] nums, int target) {        calculate(nums, 0, 0, target);        return count;    }    public void calculate(int[] nums, int i, int sum, int target) {        if (i == nums.length) {            if (sum == target) {                count++;            }        } else {            calculate(nums, i + 1, sum + nums[i], target);            calculate(nums, i + 1, sum - nums[i], target);        }    }}

Complexity

Time

O(2^n), where `n` is the length of the `nums` array. At each step, the function branches into two recursive calls, leading to a recursion tree with `2^n` leaf nodes.

Space

O(n), where `n` is the length of the `nums` array. This space is used by the recursion call stack, which can go as deep as `n`.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Provides a clear, direct translation of the problem statement into code.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Leads to a 'Time Limit Exceeded' error on platforms like LeetCode for all but the smallest inputs.

  • Recalculates the same subproblems multiple times.

Solutions

class Solution {public  int findTargetSumWays(int[] nums, int target) {    int s = 0;    for (int v : nums) {      s += v;    }    if (s < target || (s - target) % 2 != 0) {      return 0;    }    int n = (s - target) / 2;    int[] dp = new int[n + 1];    dp[0] = 1;    for (int v : nums) {      for (int j = n; j >= v; --j) {        dp[j] += dp[j - v];      }    }    return dp[n];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem