https://leetcode-cn.com/problems/combination-sum-iv/
最开始的想法是使用如下的回溯法，结果超时了，想想的确回溯的规模会特别大（特别是有1存在的时候）需要寻找更高效的解决方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void getAll(vector<int>& nums, int target, int& result) {
for(int n:nums) {
int t = target-n;
if(t == 0) ++result;
else if(t > 0) getAll(nums, t, result);
else break;
}
}
int combinationSum4(vector<int>& nums, int target) {
int result = 0;
sort(nums.begin(), nums.end());
getAll(nums, target, result);
return result;
}
};
|
使用DP后发现运行不会超时。
主要思路为使用一个名为records的map记录从1到target的所有历史答案。可以借助历史答案得到当前的答案。
需要注意的是map的value值需要设定为long，否则可能会overflow。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
sort(nums.begin(), nums.end());
map<int, long> records;
for(int n:nums) records.insert(make_pair(n, 1));
for(int i=nums[0]; i<=target; ++i) {
int t = 0;
if(records.find(i) == records.end()) records.insert(make_pair(i, 0));
for(int n:nums) {
if(i-n < 0) break;
if(records.find(i-n) != records.end()) t += records[i-n];
}
records[i] += t;
}
return records[target];
}
};
|
使用数组替换map，可以进一步提升运行效率。另外，还可以使用语句if(records[i] > INT_MAX-records[i-n]) break;判断target为某值的时候是否超过INT_MAX，如果超过，就没必要继续计算了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.size() == 0) return 0;
vector<int> records(target+1, 0);
records[0] = 1;
for(int i=1; i<=target; ++i) {
for(int n:nums) {
if(i-n < 0) continue;
if(records[i] > INT_MAX-records[i-n]) continue;
records[i] += records[i-n];
}
}
return records[target];
}
};
|