题目

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

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

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

示例 1:

  1. 输入: k = 3, n = 7
  2. 输出: [[1,2,4]]
  3. 解释:
  4. 1 + 2 + 4 = 7
  5. 没有其他符合的组合了。

示例 2:

  1. 输入: k = 3, n = 9
  2. 输出: [[1,2,6], [1,3,5], [2,3,4]]
  3. 解释:
  4. 1 + 2 + 6 = 9
  5. 1 + 3 + 5 = 9
  6. 2 + 3 + 4 = 9
  7. 没有其他符合的组合了。

示例 3:

  1. 输入: k = 4, n = 1
  2. 输出: []
  3. 解释: 不存在有效的组合。
  4. 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

    解题方法

    递归+剪枝

    递归处理每一位数，从1向9进行穷举，下一位数从当前位选取的数字下一个开始，达到9或者达到n/k。
    C++代码：
    1. class Solution {
    2. public:
    3.   void backtracking(int k, int n, int start, vector<vector<int>>& result, vector<int>& cur) {
    4.       if(!k && !n) {
    5.           result.push_back(cur);
    6.           return;
    7.       }
    8.       else if(!k || !n)   return;
    9.       else {
    10.           int upper = n/k+1;            // 剪枝
    11.           for(int i=start; i<10&&i<=upper; i++) {
    12.               cur.push_back(i);
    13.               backtracking(k-1, n-i, i+1, result, cur);
    14.               cur.pop_back();
    15.           }
    16.       }
    17.   }
    18.   vector<vector<int>> combinationSum3(int k, int n) {
    19.       vector<vector<int>> result;
    20.       vector<int> cur;
    21.       backtracking(k, n, 1, result, cur);
    22.       return result;
    23.   }
    24. };