377. Combination Sum IV

377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Solution

记忆化搜索,memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。

递归DFS,记忆化剪枝,如果memo[]数组不为空,则直接返回记忆内容。
当total等于target时,该组合成立,返回1。

遍历nums[]数组中的每个元素,并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。

*非常奇怪的是,当我使用int[]数组进行记忆化搜索时部分case会超时,推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
int[] numbers;
Integer[] memo;
public int combinationSum4(int[] nums, int target) {
numbers = nums;
memo = new Integer[target+1];
return count(0, target);
}

private int count(int total, int target){
if(memo[total] != null) return memo[total];
if(total == target) return 1;

int sum = 0;
for(int i = 0; i < numbers.length; i++){
if(total + numbers[i] <= target) sum += count(total + numbers[i], target);
}
memo[total] = sum;

return memo[total];
}
}
Author

Xander

Posted on

2022-08-05

Updated on

2022-08-05

Licensed under

Comments