Target Sum: the idea to remember.

The core insight

Branch on adding or subtracting the next value and cache the number of successful suffixes for each state.

Why it works

Two prefixes at the same index and total have identical future choices, so their suffix counts can be reused.

The mistake to avoid

Zero still has two sign choices. Include both the array index and current total in the memo key.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Branch on adding or subtracting the next value and cache the number of successful suffixes for each state.
HashMap<String, Integer> dp;

public int findTargetSumWays(int[] nums, int S) {
    dp = new HashMap<>();
    return calculate(nums, 0, 0, S);
}

public int calculate(int[] nums, int i, int sum, int S) {
    String s = i + "," + sum;

    if (i == nums.length) {
       return (sum == S)? 1 : 0; 
    }
    if(dp.containsKey(s)){
        return dp.get(s); 
    }

    int res = calculate(nums, i + 1, sum + nums[i], S) + calculate(nums, i + 1, sum - nums[i], S);
    dp.put(s, res);
    return res;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection