Target Sum

Leetcode Problem:

• Target Sum

Summary

• Find the number of different expressions that can be built from the given integer array and target sum.

Approach

• Dynamic programming with memoization
• The function recursively tries all possible combinations of '+' and '-' operations before the current number and stores the results in a memoization table to avoid redundant calculations.

Complexity

• O(n * sum), where n is the length of the input array and sum is the target sum.

Explanation

• The solution uses a recursive function with memoization to try all possible combinations of '+' and '-' operations before the current number
• The memoization table stores the results of subproblems to avoid redundant calculations
• The base cases are when the current index is 0 (no more numbers to process) or when the sum equals the target
• The function returns 1 if the sum equals the target and 0 otherwise
• The results are stored in the memoization table and returned.

Solution Code:

class Solution {
public:
    int memo[20][2001];
    int findTargetSumWays(vector& nums, int target, int cur=0, int sum=0) {
        if(cur == 0){
            memset(memo, -1, sizeof(memo));
        }
        if(cur == nums.size()){
            if (sum == target){
                return 1;
            }
            return 0;
        }
        if(memo[cur][sum+1000] != -1) return memo[cur][sum+1000];
        int res = 0;
        res += findTargetSumWays(nums, target, cur+1, sum + nums[cur]);
        res += findTargetSumWays(nums, target, cur+1, sum - nums[cur]);
        return memo[cur][sum+1000] = res;
    }
};