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;
}
}