package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/combination-sum-iv/
 */
public class Problem377 {
    public int combinationSum4(int[] nums, int target) {
        return combinationSum(nums, target, new HashMap<>());
    }

    private int combinationSum(int[] nums, int target, Map<Integer, Integer> memo) {
        if (target < 0) {
            return 0;
        }
        if (target == 0) {
            return 1;
        }
        if (memo.containsKey(target)) {
            return memo.get(target);
        }
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += combinationSum(nums, target - nums[i], memo);
        }
        memo.put(target, count);
        return count;
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -152,24 +152,74 @@
 t target) %7B%0A
+        Integer%5B%5D memo = new Integer%5Btarget + 1%5D;%0A
         retu
@@ -227,32 +227,33 @@
 n combinationSum
+4
 (nums, target, n
@@ -255,23 +255,12 @@
 et, 
-new HashMap%3C%3E()
+memo
 );%0A 
@@ -277,16 +277,23 @@
 private 
+static 
 int comb
@@ -302,16 +302,17 @@
 ationSum
+4
 (int%5B%5D n
@@ -332,29 +332,17 @@
 et, 
-Map%3C
 Integer
-, Integer%3E
+%5B%5D
  mem
@@ -483,28 +483,24 @@
 memo
-.containsKey(target)
+%5Btarget%5D != null
 ) %7B%0A
@@ -526,20 +526,16 @@
 memo
-.get(
+%5B
 target
-)
+%5D
 ;%0A  
@@ -554,21 +554,22 @@
     int 
-count
+answer
  = 0;%0A  
@@ -626,21 +626,22 @@
         
-count
+answer
  += comb
@@ -650,16 +650,17 @@
 ationSum
+4
 (nums, t
@@ -709,27 +709,25 @@
 memo
-.put(
+%5B
 target
-, count)
+%5D = answer
 ;%0A  
@@ -743,13 +743,14 @@
 urn 
-count
+answer
 ;%0A  

Update problem 377