本文共 1029 字，大约阅读时间需要 3 分钟。

1. 题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：所有数字都是正整数。解集不能包含重复的组合。 示例 1:输入: k = 3, n = 7输出: [[1,2,4]]示例 2:输入: k = 3, n = 9输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/combination-sum-iii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

相关题目

2. 回溯解题

• 关键在于如何避免重复
• 每次取了一个数 i ，那么下次取得数只能比 i 大，这样避免重复组合

class Solution {
   public:    vector
   
    
     > combinationSum3(int k, int n) {
           vector
     
      
       > ans;        vector
       
         cb;        bt(0,0,k,0,n,cb,ans);        return ans;    }    void bt(int num, int count, int k, int sum, int n, vector
        
          &cb, vector
         
          
           > &ans) { if(sum > n || 9-num < k-count)//和超了，或者剩余的数不够个数 return; if(count == k) { if(sum == n) ans.push_back(cb); return; } for(int j = num+1; j <= 9; ++j)//每次取num+1，避免重复 { cb.push_back(j); bt(j,count+1,k,sum+j,n,cb,ans); cb.pop_back(); } }};
          
         
        
       
      
     
    
   

0 ms 6.8 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/101369537 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！