Combination Sum IV
给一个数组和一个target, 求这个数组中有多少种数字组合可以组成这个target.
dfs + memo 模板题.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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; } } |