LeetCode 216 Combination Sum III（Backtracking）（*）

翻译

找出所有的k个数字相加得到数字n的组合，只有1到9的数字可以被使用，并且每个组合间需要是不同的数字集。

原文

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7
Output:
[[1,2,4]]

Example 2:

Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]

分析

这类找组合的题目一般都可以用回溯法解决。

可以这样理解，如果要用暴力法的话，如果是有3个数字相加，那就需要3套for循环，4个数字就需要4套for循环，然而我们并不知道会有几个数字。

那么回溯法解决了什么问题？

看看下面的结果集，我们需要不断的横向加数字进来，然后纵向加组合，并且不断的横向、纵向结合。回溯法能够让每一行的数字加到末尾之后，能够继续往回（也就是往左）走。

没法话动图，说得详细点吧：
当横向走到第一行的9时候，退到8，回溯回来之和将9继续加1，但题目要求每个数字都在1到9之间。所以，我们要在代码中加以约束。

继续退到2，它可以往上加到3。

INPUT : 4, 20
OUTPUT:
1 2 8 9
1 3 7 9
1 4 6 9
1 4 7 8
1 5 6 8
2 3 6 9
2 3 7 8
2 4 5 9
2 4 6 8
2 5 6 7
3 4 5 8
3 4 6 7

另外，题中的n值得是需要加到和，但在我们用于回溯的函数中，n更确切的是代表了还需要相加的和。比如说题目要求加到20，如果已经添加了数字1，那么还需要加上19，所以此时n会等于19。但一共需要的数字，比如说4，它是不变的。变化的是每一个组合的size。

接着来看看应该有哪些约束条件：
1）组合.size == k 并且 n == 0，此时这个组合已经完成了，只要将它添加到组合集中并退出即可。
2）如果组合.size < k，这表明还需要进一步的向这个组合添加数字进去。
2-a）继续看上面的那个结果集，如果组合的长度还是等于0，此时就没有数字在里面，那么我们就从0开始计数。否则就在上一个数的基础上加1。
2-b）不论如何，始终要保证加的几个数字不能超过要求的和，比如要求一共加到20，那么就不能让那些数字加到21。
2-c）每次将数字加入到组合中之和，我们要在这个组合的基础上弹出最后一个数字以开启下一次组合的计算。

代码

class Solution {
public:
void combination3(vector<vector<int>>& result, vector<int> combi, int k, int n) {
    if (combi.size() == k && n == 0) {
        result.push_back(combi);
        return;
    } else if (combi.size() < k) {
        for (int i = combi.empty() ? 1 : combi.back() + 1; i < 10; i++) {
            if (n - i < 0) break;
            combi.push_back(i);
            combination3(result, combi, k, n - i);
            combi.pop_back();
        }
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> result;
    vector<int> combi;
    combination3(result, combi, k, n);
    return result;
}
};