216. 组合总和 III

找出所有相加之和为 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]]

本题是很简单的回溯算法，其实也就是递归，既然是递归那就需要确定递归终止条件，判断递归中需要做什么。
1、递归终止条件就是，当一个组合中有3个数字，那就是递归结束，并且还得判断组合中的数字和是否等于给定的n。
2、在递归过程中就是将一个个数字加入组合，是很简单的。注意是不能重复的，那就是需要一个有序，代码中以升序为例子，每次加入的数字都要比之前的数字大。

代码如下：

class Solution {
private:
    vector<vector<int>> ans;
    bool *visit;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        visit=new bool [10];
        for(int i=1;i<10;i++) visit[i]=false;
        traceback(vector<int>(),0,1,k,n);
        return ans;
    }
    void traceback(vector<int> tmp,int sum,int start,int k,int n){
        if( k == 0 ){
            if( sum == n )
            ans.push_back(tmp);
            return ;
        }
        for(int i=start;i<=9;i++){
            if(visit[i]==true){
                continue;
            }
            if( sum+i > n ){
                break;
            }
            visit[i]=true;
            tmp.push_back(i);
            traceback(tmp,sum+i,i+1,k-1,n);
            tmp.pop_back();
            visit[i]=false;
        }
    }
};

这个几乎可以成为一个解决回溯的模板，也是我个人总结归纳出来的。可以参照我的另外一篇博客也是回溯算法的解题，两个代码几乎一模一样。几乎也确实可以解决任何的回溯问题，剪枝也只是在这个模板上修改一二即可。

传送门：https://www.jianshu.com/p/8eb949d4859b

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。