AlgoDaily - Feature: Solving the Target Sum problem with dynamic programming and more

Home > Data Structures and Algorithms 🚀 > Hash Maps and Key Values > Feature: Solving the Target Sum problem with dynamic programming and more

Solution 2: Recursion with memoization

Notice how in the previous solution we end up re-computing the solutions to sub-problems. We could optimize this by caching our solutions using memoization.

Notice how the twist in the problem --- forcing us to either add or subtract a number --- has already complicated the solution. We are forced to either use an offset of +1000 to the array index (question stipulates that the sum of elements in the array ≤ 1000) to account for negative values (since we can't have negative indices in an array), or use a HashMap (Java)/dictionary (Python) instead.

I went with the former, because the overhead of using a Hashmap significantly increased the runtime (you can try both and compare!).

xxxxxxxxxx
}
 
import java.util.Arrays;
​
class Main {
    public static int findTargetSumWays(int[] nums, int s) {
        int[][] memo = new int[nums.length + 1][2001];
        for (int[] row: memo) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
​
        return backtrack(memo, nums, 0, 0, s);
    }
​
    private static int backtrack(int[][] memo,
            int[] nums,
            int index,
            int sum,
            int s) {
        if (index == nums.length) {
            return sum == s ? 1 : 0;
        }
​
        if (memo[index][sum + 1000] != Integer.MIN_VALUE) {
            return memo[index][sum + 1000];
        }
​
        int ans =
            backtrack(memo, nums, index + 1, sum + nums[index], s) +
            backtrack(memo, nums, index + 1, sum - nums[index], s);
        memo[index][sum + 1000] = ans;

Solution 2: Recursion with memoization

Programming Categories

Popular Lessons