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.
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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000This approach utilizes recursive backtracking to explore all possible combinations of adding '+' or '-' in front of each number. To optimize, we use memoization to cache the results of previously computed states, which reduces recalculations and improves efficiency.
In the Python solution, we define a recursive function backtrack that takes the index of the current number and the total, which is the current calculated sum. We use memoization to store already calculated states, which ensures each recursive path is only computed once. At each step, we decide to either add or subtract the current number, continuing until all numbers are used. The base case checks if the formed expression equals target.
C++
Time Complexity: O(n * sum(nums)), where n is the number of elements.
Space Complexity: O(n * sum(nums)) for the memoization storage.
This approach utilizes a 2D dynamic programming table. We determine how many ways the numbers can sum to a potential value (positive or negative).
The Java solution initializes a 2D array dp, where dp[i][j] represents the number of ways the first i numbers can add up to j - sum. We initialize dp[0][sum] to 1 to account for starting from zero. We iterate through the numbers, updating the dp table to account for all possible sums achievable by adding or subtracting each number.
JavaScript
Time Complexity: O(n * 2 * sum), where n is the number of elements.
Space Complexity: O(n * 2 * sum) due to the DP table storage.
| Approach | Complexity |
|---|---|
| Recursive Backtracking with Memoization | Time Complexity: O(n * sum(nums)), where n is the number of elements. |
| 2D Dynamic Programming Table | Time Complexity: O(n * 2 * sum), where n is the number of elements. |
Two Sum - Leetcode 1 - HashMap - Python • NeetCode • 1,640,492 views views
Watch 9 more video solutions →Practice Target Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor