思路
回溯法
代码
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
public:
void function(int k, int n, int startindex, int sum)
{
int i;
// 剪枝
// 超过了, 不用找了;
if(sum > n)
{
return;
}
// 找到k个数了
if(path.size() == k)
{
if(sum == n)
{
result.push_back(path);
}
return;
}
// 题目提示了从[1, 9]中找
for(i = startindex; i <= 9; i++)
{
// 剪枝
// 需要找的数量 > 剩余的数量
if((k - path.size()) > (9 - i + 1))
{
break;
}
sum += i;
path.push_back(i);
function(k, n, i+1, sum);
sum -= i;
path.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
result.clear();
path.clear();
function(k, n, 1, 0);
return result;
}
};
有2处剪枝哦!