Leetcode 216.组合总和Ⅲ 回溯+剪枝 C++实现

Leetcode 216.组合总和Ⅲ

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

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

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

算法：

创建二维返回数组 ans ，临时数组 path 。

进入函数 dfs ，边界条件是 d==0 即剩余应选数字个数为 0 ，则可以 return 。如果剩余数字不符合条件，则直跳过，进入下一个循环。

代码：

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> ans;// 返回数组ansvector<int> path;// 临时数组path// 剩余可选择的数字个数i，还需选的数字大小之和tauto dfs = [&](auto &&dfs,int i,int t){int d = k - path.size();// 还需选择的数字个数dif(t < 0 || t > (2*i-d+1)*d/2)  return ;// 剩余数字不符合// 选好了if(d == 0){ans.emplace_back(path);return ;}for(int j = i;j >= d;j--){path.push_back(j);dfs(dfs,j-1,t-j);path.pop_back();// 恢复现场}};dfs(dfs,9,n);return ans;}
};