Target Sum [memoization DP]

117.Target Sum

Dynamic Programming

Recursion

Problem Statement:

You are given an integer array nums and an integer S. You need to find the total number of ways to assign '+' and '-' symbols to elements in the array such that their sum equals S.

Algorithm:

1. Use recursion to explore all combinations of adding and subtracting the numbers in the array.
2. Memoize intermediate results to avoid redundant calculations:
   • Store the result of a subproblem with parameters (i, sum), where i is the current index and sum is the current total.
   • The key for memoization is offset by 1000 to handle negative sums.
3. Base case: If all elements are used (i == nums.length), check if the current sum equals S.
4. Recursive case:
   • Add the current number to the sum and recurse.
   • Subtract the current number from the sum and recurse.
   • Store the total number of ways in the memo table.

Complexity:

Time: O(n × 2000), where n is the length of nums, and 2000 accounts for all possible sums from -1000 to 1000 | Space: O(n × 2000), for memoization.

Java Implementation:

import java.util.Arrays;

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int[][] memo = new int[nums.length][2001];
        for (int[] row : memo) Arrays.fill(row, -1);
        return findTarget(nums, S, 0, 0, memo);
    }

    private int findTarget(int[] nums, int S, int sum, int index, int[][] memo) {
        if (index == nums.length) return sum == S ? 1 : 0;
        if (memo[index][sum + 1000] != -1) return memo[index][sum + 1000];

        // Explore both adding and subtracting the current number
        int add = findTarget(nums, S, sum + nums[index], index + 1, memo);
        int subtract = findTarget(nums, S, sum - nums[index], index + 1, memo);

        // Memoize and return the total ways
        return memo[index][sum + 1000] = add + subtract;
    }
}
                

Python Implementation:

def findTargetSumWays(nums, S):
    memo = {}

    def findTarget(index, curr_sum):
        if index == len(nums):
            return 1 if curr_sum == S else 0
        if (index, curr_sum) in memo:
            return memo[(index, curr_sum)]

        # Explore adding and subtracting the current number
        add = findTarget(index + 1, curr_sum + nums[index])
        subtract = findTarget(index + 1, curr_sum - nums[index])

        memo[(index, curr_sum)] = add + subtract
        return memo[(index, curr_sum)]

    return findTarget(0, 0)
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int findTargetSumWays(vector& nums, int S) {
        vector> memo(nums.size(), vector(2001, -1));
        return findTarget(nums, S, 0, 0, memo);
    }

    int findTarget(vector& nums, int S, int sum, int index, vector>& memo) {
        if (index == nums.size()) return sum == S ? 1 : 0;
        if (memo[index][sum + 1000] != -1) return memo[index][sum + 1000];

        // Explore adding and subtracting the current number
        int add = findTarget(nums, S, sum + nums[index], index + 1, memo);
        int subtract = findTarget(nums, S, sum - nums[index], index + 1, memo);

        // Memoize and return the total ways
        return memo[index][sum + 1000] = add + subtract;
    }
};