Combination Sum IV

给一个数组和一个target, 求这个数组中有多少种数字组合可以组成这个target.

dfs + memo 模板题.

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    public int combinationSum4(int[] nums, int target) { // dfs + memo
        if(target < 0)
            return 0;
        if(target == 0)
            return 1;
        if(memo.containsKey(target))
            return memo.get(target);
        int cur = 0;
        for(int n : nums){
            cur += combinationSum4(nums, target - n); // sum = target - 1 , target - 2, target - 3
        }
        memo.put(target, cur);
        return cur;
    }
}