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.
1#include <unordered_map>
2#include <vector>
3
4int backtrack(std::unordered_map<int, int>& memo, const std::vector<int>& nums, int target, int index, int total) {
5 if (index == nums.size()) {
6 return total == target ? 1 : 0;
7 }
8 int key = index * 2001 + total;
9 if (memo.find(key) != memo.end()) {
10 return memo[key];
11 }
12 int positive = backtrack(memo, nums, target, index + 1, total + nums[index]);
13 int negative = backtrack(memo, nums, target, index + 1, total - nums[index]);
14 memo[key] = positive + negative;
15 return memo[key];
16}
17
18int findTargetSumWays(std::vector<int>& nums, int target) {
19 std::unordered_map<int, int> memo;
20 return backtrack(memo, nums, target, 0, 0);
21}The C++ solution follows a similar pattern as the Python version, using a helper function backtrack to compute the number of expressions. We create a key for the memoization map using the index and total to uniquely identify each state. The recursive function calls itself with the next index to either add or subtract the current number, and the results are stored in a map for quick retrieval.
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.
1public class Solution {
2 public int findTargetSumWaysThe 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.