回溯算法指组合总和

题目：

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路：

这种问题是需要遍历每一个数排练组合一下。可以看到这是一个递减的n叉树

最多为9个数，实际数量为k个数。

所以结束条件就是判断数组数量是否为k，for循环里面是9

并且需要一个sum和一个index来辅助回溯算法

看代码

class Solution {
public:vector<vector<int>> result;vector<int> path;void huisu(int n,int k,int sum,int startIndex){if(path.size() == k ){if(sum == n){result.push_back(path);}return;}for(int i = startIndex; i <= 9;i++){sum += i;path.push_back(i);huisu(n,k,sum,i+1);sum -= i;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {huisu(n,k,0,1);return result;}
};