算法 - 组合总和3

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

216. 组合总和 III - 力扣（LeetCode）

题目描述

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

只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例

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

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

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

提示

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

题目解析

本题相当于是 从[1,9]这9个数中取k个的组合问题。另外，当k位组合生成后，判断组合数之和是否为n,若为n才是本题的解。

上面逻辑并不难。

本题应该更关注剪枝优化方面，本题有两个地方可以进行剪枝

• 每层节点可选择的范围，即for循环范围，由于必须选k个数，则对于组合问题而言，每一层的节点选择的起始位置应该从 N - (k - path.length) + 1 开始，N，k表示组合是从N个数中选择k个
• 如果在进入递归之前，组合数之和已经大于n了，则没有必要继续递归了，因为继续递归只会新增组合数，让组合数之和更大

回溯函数的参数优化，本题可以一般都会为回溯函数定义一个sum参数，用于保存组合数之和，来与n进行比较，若sum > n，则剪枝，若sum === n && path.length === k，则组合数为题解。可以发现sum就是用于和n比较的，我们完全可以将sum的工作交给n参数，即将sum += i的工作变为 n - i。

算法源码

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
  const result = [];
  backTracking(1, k, n, [], result);
  return result;
};
 
function backTracking(start, k, n, path, result) {
  if (path.length === k) {
    if (n === 0) result.push([...path]);
    return;
  }
 
  for (let i = start; i <= 9 - (k - path.length) + 1; i++) {
    if (n < 0) break;
    path.push(i);
    backTracking(i + 1, k, n - i, path, result);
    path.pop();
  }
}