216. 组合总和 III
题目描述
输入两个整数 k 和 n。从数字 1 到 9 中选出 k 个，使它们的和恰好为 n。每个数字最多选一次。
返回所有满足条件的组合。同一组合不能重复出现，组合之间的顺序随意。
示例 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、1 + 3 + 5、2 + 3 + 4 都等于 9。
示例 3
输入：k = 4, n = 1 输出：[]
解释：4 个不同数字的和至少是 1 + 2 + 3 + 4 = 10，大于 1，不存在组合。
数据范围
2 <= k <= 91 <= n <= 60
解题思路：回溯 + 剪枝
回溯：path 保持升序，dfs(start, remain) 从 start..9 中挑下一个数。选满 k 个时检查 remain 是否为 0。因为枚举是升序的，一旦 x > remain，后面更大的数也不行，直接 break。
为什么正确
remain = n − sum(path)，且 path 严格递增、每个元素都 < start。
复杂度分析
至多枚举 1–9 的 C(9,k) 个子集，时间 O(C(9,k)·k)；递归深度 O(k)。
易错点
选满 k 个但和不对时也要 return，否则会继续选更多的数；break 只在升序枚举时才正确。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res, path = [], []
def dfs(start, remain):
if len(path) == k:
if remain == 0:
res.append(path[:])
return
for x in range(start, 10):
if x > remain:
break
path.append(x)
dfs(x + 1, remain - x)
path.pop()
dfs(1, n)
return resclass Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int k;
public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;
dfs(1, n);
return res;
}
void dfs(int start, int remain) {
if (path.size() == k) {
if (remain == 0) {
res.add(new ArrayList<>(path));
}
return;
}
for (int x = start; x < 10; x++) {
if (x > remain) {
break;
}
path.add(x);
dfs(x + 1, remain - x);
path.remove(path.size() - 1);
}
}
}class Solution {
vector<vector<int>> res;
vector<int> path;
int k;
void dfs(int start, int remain) {
if ((int)path.size() == k) {
if (remain == 0) {
res.push_back(path);
}
return;
}
for (int x = start; x < 10; x++) {
if (x > remain) {
break;
}
path.push_back(x);
dfs(x + 1, remain - x);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
this->k = k;
dfs(1, n);
return res;
}
};func combinationSum3(k int, n int) [][]int {
res, path := [][]int{}, []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if len(path) == k {
if remain == 0 {
res = append(res, append([]int{}, path...))
}
return
}
for x := start; x < 10; x++ {
if x > remain {
break
}
path = append(path, x)
dfs(x+1, remain-x)
path = path[:len(path)-1]
}
}
dfs(1, n)
return res
}var combinationSum3 = function(k, n) {
const res = [], path = [];
const dfs = (start, remain) => {
if (path.length === k) {
if (remain === 0) {
res.push([...path]);
}
return;
}
for (let x = start; x < 10; x++) {
if (x > remain) {
break;
}
path.push(x);
dfs(x + 1, remain - x);
path.pop();
}
};
dfs(1, n);
return res;
};function combinationSum3(k: number, n: number): number[][] {
const res: number[][] = [], path: number[] = [];
const dfs = (start: number, remain: number): void => {
if (path.length === k) {
if (remain === 0) {
res.push([...path]);
}
return;
}
for (let x = start; x < 10; x++) {
if (x > remain) {
break;
}
path.push(x);
dfs(x + 1, remain - x);
path.pop();
}
};
dfs(1, n);
return res;
}其他解法
子集枚举不加筛选地检查全部 2^9 种选法；回溯按顺序构造组合，在数量或和已经不可能满足时提前剪枝，只访问有希望的分支。
解法 2：二进制（子集）枚举 时间 O(2^9·9)，空间 O(k)
1 到 9 每个数字只有“选”和“不选”两种状态，用一个 9 位二进制数 mask 表示一种选法：第 i 位为 1 表示选了数字 i+1。枚举 0 到 2^9-1 的所有 mask，取出对应的数字，如果恰好选了 k 个且和为 n，就加入答案。
没有递归，只是一个二重循环，很好理解。之所以可行是因为总共只有 512 种子集；它不能剪枝，候选集合变大时不如回溯。
from typing import List
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
res = []
for mask in range(1 << 9):
path = [i + 1 for i in range(9) if mask >> i & 1]
if len(path) == k and sum(path) == n:
res.append(path)
return resclass Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
for (int mask = 0; mask < (1 << 9); mask++) {
List<Integer> path = new ArrayList<>();
int sum = 0;
for (int i = 0; i < 9; i++) {
if ((mask >> i & 1) == 1) {
path.add(i + 1);
sum += i + 1;
}
}
if (path.size() == k && sum == n) res.add(path);
}
return res;
}
}class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
for (int mask = 0; mask < (1 << 9); mask++) {
vector<int> path;
int sum = 0;
for (int i = 0; i < 9; i++) {
if (mask >> i & 1) {
path.push_back(i + 1);
sum += i + 1;
}
}
if ((int)path.size() == k && sum == n) res.push_back(path);
}
return res;
}
};func combinationSum3(k int, n int) [][]int {
res := [][]int{}
for mask := 0; mask < 1<<9; mask++ {
path := []int{}
sum := 0
for i := 0; i < 9; i++ {
if mask>>i&1 == 1 {
path = append(path, i+1)
sum += i + 1
}
}
if len(path) == k && sum == n {
res = append(res, path)
}
}
return res
}var combinationSum3 = function(k, n) {
const res = [];
for (let mask = 0; mask < (1 << 9); mask++) {
const path = [];
let sum = 0;
for (let i = 0; i < 9; i++) {
if ((mask >> i) & 1) {
path.push(i + 1);
sum += i + 1;
}
}
if (path.length === k && sum === n) res.push(path);
}
return res;
};function combinationSum3(k: number, n: number): number[][] {
const res: number[][] = [];
for (let mask = 0; mask < (1 << 9); mask++) {
const path: number[] = [];
let sum = 0;
for (let i = 0; i < 9; i++) {
if ((mask >> i) & 1) {
path.push(i + 1);
sum += i + 1;
}
}
if (path.length === k && sum === n) res.push(path);
}
return res;
};