算法-回溯篇02-组合总和 III
组合总和 III
力扣题目链接
题目描述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
解题思路
这道题目其实数据量小，使用回溯主要还是为了学会它。
和上一题类似，这里我对于回溯的做法如下：
- 记录下剩下需要的数字的数量，每次选取一个数字把数量减一；
- 把相加目标之和减去当前数据；
- 后面的数字长度要保证大于等于需要选取的长度；i < 10 - k
- 当前选取的数据要小于等于剩下的数据大小；i <= n
- 当剩余数为0且剩余相加目标之和也为0时返回一个路径。
题解
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void backTracking(int k, int n, int startIndex){
k--;
if(k == -1 && n == 0){
ans.push_back(path);
}
for(int i = startIndex; i <= n && i < 10 - k; i++){
path.push_back(i);
backTracking(k, n - i, i + 1);
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backTracking(k, n, 1);
return ans;
}
};