https://leetcode-cn.com/problems/combination-sum-iii/
思路和之前两道题（Combination Sum和Combination Sum II）类似，都是使用回溯法，回溯的时候判断数字个数以及数字之和即可，另外还需要使用一个参数s去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
void getAll(vector<vector<int>>& result, vector<int>& record, int k, int n, int s) {
for(int i=s; i<=9 && i<=n; ++i) {
if(n-i > 0) {
record.push_back(i);
getAll(result, record, k-1, n-i, i+1);
record.pop_back();
} else if(n-i == 0) {
if(k-1 == 0) {
vector<int> record_copy(record);
record_copy.push_back(i);
result.push_back(record_copy);
}else break;
} else break;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> record;
getAll(result, record, k, n, 1);
return result;
}
};
|