C++刷leetcode（216. 组合总和 III）【回溯】

糖逗

题目描述：

1. 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
   
2. 
   
3. 说明：
   
4. 
   
5. 所有数字都是正整数。
   
6. 解集不能包含重复的组合。 
   
7. 示例 1:
   
8. 
   
9. 输入: k = 3, n = 7
   
10. 输出: [[1,2,4]]
    
11. 示例 2:
    
12. 
    
13. 输入: k = 3, n = 9
    
14. 输出: [[1,2,6], [1,3,5], [2,3,4]]
    
15. 
    
16. 来源：力扣（LeetCode）
    
17. 链接：https://leetcode-cn.com/problems/combination-sum-iii
    
18. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(int k, int n, vector<vector<int> > & res, vector<int>& temp, int cur, int sum){
   
4.         if(temp.size() > k) return;
   
5.         if(temp.size() == k){
   
6.             if(sum == n)res.push_back(temp);
   
7.             else if(sum != n) return;
   
8.         }
   
9.         if(k-temp.size() > 0){
   
10.             int store = 9 < (n-sum)/(k-temp.size()) ? 9 : (n-sum)/(k-temp.size());
    
11.             for(int i = cur + 1; i <= store; i++){
    
12.                 temp.push_back(i);
    
13.                 dfs(k, n, res, temp, i, sum + i);
    
14.                 temp.pop_back();
    
15.             }
    
16.         }
    
17.     }
    
18.     vector<vector<int>> combinationSum3(int k, int n) {
    
19.         vector<vector<int> > res;
    
20.         vector<int> temp;
    
21.         dfs(k, n, res, temp, 0, 0);
    
22.         return res;
    
23.     }
    
24. };

复制代码