0216. 组合总和 III【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 回溯

1. 📝 题目描述

• leetcode

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

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

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

---

示例 1：

输入: k = 3, n = 7
输出: [[1,2,4]]

解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2：

输入: 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
没有其他符合的组合了。

示例 3：

输入: k = 4, n = 1
输出: []

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

---

提示：

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

2. 🎯 s.1 - 回溯

c

void backtrack(int start, int remain, int k, int* path, int pathLen, int** res, int* resSize, int** resColSize) {
    if (pathLen == k) {
        if (remain == 0) {
            res[*resSize] = (int*)malloc(sizeof(int) * k);
            memcpy(res[*resSize], path, sizeof(int) * k);
            (*resColSize)[*resSize] = k;
            (*resSize)++;
        }
        return;
    }
    for (int i = start; i <= 9; i++) {
        if (i > remain) break;
        path[pathLen] = i;
        backtrack(i + 1, remain - i, k, path, pathLen + 1, res, resSize, resColSize);
    }
}

int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {
    int** res = (int**)malloc(sizeof(int*) * 200);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 200);
    *returnSize = 0;
    int path[9];
    backtrack(1, n, k, path, 0, res, returnSize, returnColumnSizes);
    return res;
}

js

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

py

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        def backtrack(start, remain, path):
            if len(path) == k:
                if remain == 0:
                    res.append(path[:])
                return
            for i in range(start, 10):
                if i > remain:
                    break
                path.append(i)
                backtrack(i + 1, remain - i, path)
                path.pop()
        backtrack(1, n, [])
        return res

• 时间复杂度：$O(C(9,k))$，从 9 个数中选 $k$ 个的组合数
• 空间复杂度：$O(k)$，递归栈深度

算法思路：

• 从 1–9 中选择 $k$ 个不重复的数使其和为 $n$
• 回溯搜索，当剩余值小于当前数时剪枝