- 分析
回溯框架,关键要理解backtrack函数像一个指针在决策树上游走的含义。
- 代码
class Solution {
public:
vector<vector<int>> vec;
int k,n;
vector<vector<int>> combinationSum3(int k, int n) {
this -> k = k;
this -> n = n;
vector<int> temp;
int sum = 0;
backtrack(1, temp, 0);
return vec;
}
void backtrack(int start, vector<int>& temp, int sum){
//结束条件
if(k == temp.size() && sum == n){
vec.push_back(temp);
}
for(int i = start; i < 10; i++){
//选择条件
if(sum + i > n) continue;
//做选择
sum += i;
temp.push_back(i);
backtrack(i + 1, temp, sum);
//撤销选择
sum -= i;
temp.pop_back();
}
}
};