package leetcode;

/**
 * https://leetcode.com/problems/target-sum/
 */
public class Problem494 {
    public int findTargetSumWays(int[] nums, int S) {
        return findTargetSumWays(nums, S, 0);
    }

    private static int findTargetSumWays(int[] nums, int s, int idx) {
        if (idx == nums.length) {
            return (s == 0) ? 1 : 0;
        }
        return findTargetSumWays(nums, s - nums[idx], idx + 1) +
            findTargetSumWays(nums, s + nums[idx], idx + 1);
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -237,16 +237,33 @@
 ms, S, 0
+, new HashMap%3C%3E()
 );%0A    %7D
@@ -331,16 +331,43 @@
  int idx
+, Map%3CString, Integer%3E memo
 ) %7B%0A    
@@ -443,38 +443,161 @@
       %7D%0A        
-return
+String key = s + %22%7C%22 + idx;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        int answer =
  findTargetSumWa
@@ -627,16 +627,22 @@
  idx + 1
+, memo
 ) +%0A    
@@ -695,17 +695,77 @@
  idx + 1
-)
+, memo);%0A        memo.put(key, answer);%0A        return answer
 ;%0A    %7D%0A

Update problem 494