Target Sum
Problem Description
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'+'before2and a'-'before1and 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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
Solve it on LeetCode
Approaches
1. Recursive Backtracking
The first approach uses recursion to explore all possible ways to add or subtract numbers from the array to achieve the target sum.
Intuition:
For each number in the array, you have two choices:
- Add it to the running total.
- Subtract it from the running total.
By recursively exploring both these choices, you can determine if the target sum can be achieved. This will involve exploring all 2^n combinations, where n is the length of the array.
Code:
- Time Complexity:
O(2^n), wherenis the number of elements in the array. This is because we are exploring both add and subtract options for each number. - Space Complexity:
O(n), due to the recursive stack space.
2. Memoization (Top-Down DP)
The recursive approach has a lot of overlapping subproblems, hence we can use memoization to store and reuse the results of these subproblems.
Intuition:
By using a hashmap to save previously computed results, we can avoid redundant calculations. The key is to store the index and the current sum as a tuple (or concatenated string) to uniquely identify each state.
Code:
- Time Complexity:
O(n * s), wherenis the length of the array andsis the sum of the array. The memoization reduces the number of recursive calls. - Space Complexity:
O(n * s), for the memoization hashmap plus stack space.
3. Dynamic Programming (Bottom-Up DP)
We can further optimize by using a bottom-up approach to construct a dp array. This transforms the problem of target sum into a subset sum problem using transformation and leads to more efficient computation.
Intuition:
Consider the equation sum(P) - sum(N) = target, where P is the positive subset and N is the negative subset. The transformation gives sum(P) = (target + sum(nums)) / 2. Hence, this reduces to counting how many ways we can pick a subset of nums that adds up to this sum.
This requires target + sum(nums) to be even and non-negative.
Code:
- Time Complexity:
O(n * s), wherenis the length of nums andsis the target sum transformed as above. - Space Complexity:
O(s), wheresis the target sum. We use an array proportional to the target sum.