Sponsored
Sponsored
This 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.
Time Complexity: O(n * sum(nums)), where n is the number of elements.
Space Complexity: O(n * sum(nums)) for the memoization storage.
1def findTargetSumWays(nums, target):
2 memo = {}
3 def backtrack(index, total):
4 if index == len(nums):
5 return 1 if total == target else 0
6 if (index, total) in memo:
7 return memo[(index, total)]
8 positive = backtrack(index + 1, total + nums[index])
9 negative = backtrack(index + 1, total - nums[index])
10 memo[(index, total)] = positive + negative
11 return memo[(index, total)]
12 return backtrack(0, 0)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.
This approach utilizes a 2D dynamic programming table. We determine how many ways the numbers can sum to a potential value (positive or negative).
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.
1function findTargetSumWays(nums, target) {
2 const sum
The JavaScript solution follows the same approach as the Java version, utilizing a 2D array to store the number of ways to reach each intermediate sum. It sets up the initial condition in the dp array, then iteratively populates the array using the input numbers, accounting for all possible plus and minus operations.