当前位置：首页 > ds >正文

LeetCode算法题(Go语言实现)_58

ds 2025/7/7 2:44:35

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

一、代码实现（回溯法）

func combinationSum3(k int, n int) [][]int {var res [][]intvar backtrack func(start int, path []int, sum int)backtrack = func(start int, path []int, sum int) {if len(path) == k {if sum == n {tmp := make([]int, k)copy(tmp, path)res = append(res, tmp)}return}for i := start; i <= 9; i++ {// 剪枝：总和超过目标值if sum+i > n {break}// 剪枝：剩余数字不足remaining := k - len(path) - 1if 9-i < remaining {break}backtrack(i+1, append(path, i), sum+i)}}backtrack(1, []int{}, 0)return res
}

二、算法分析

1. 核心思路

回溯算法：通过递归构建所有可能的数字组合
剪枝优化：
- 当当前和超过目标值时停止搜索
- 当剩余数字不足以完成组合时提前终止
有序选择：始终按升序选择数字避免重复组合

2. 关键步骤

初始化参数：起始数字1，空路径，初始和为0
递归终止条件：路径长度等于k时验证总和
剪枝处理：
- 总和超过目标值时中断循环
- 剩余数字不足时中断循环
递归构建：选择当前数字后进入下一层递归

3. 复杂度

指标	值	说明
时间复杂度	O(C(9,k))	组合数上限为C(9,k)
空间复杂度	O(k)	递归栈深度与路径长度相关

三、图解示例

在这里插入图片描述

四、边界条件与扩展

1. 特殊场景验证

最小值边界：k=1, n=1 → [[1]]
最大值边界：k=9, n=45 → [[1,2,3,4,5,6,7,8,9]]
无解情况：k=2, n=1 → []
精确匹配：k=3, n=15 → [[1,5,9],[1,6,8],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]]

2. 扩展应用

彩票组合生成：生成满足特定和值的数字组合
密码破解：尝试特定长度的数字密码组合
数学教学：演示组合数学与回溯算法的实际应用

3. 多语言实现

class Solution {public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> res = new ArrayList<>();backtrack(1, k, n, new ArrayList<>(), res);return res;}private void backtrack(int start, int k, int remain, List<Integer> path, List<List<Integer>> res) {if (path.size() == k) {if (remain == 0) res.add(new ArrayList<>(path));return;}for (int i = start; i <= 9; i++) {if (i > remain) break;if (9 - i < k - path.size() - 1) break;path.add(i);backtrack(i + 1, k, remain - i, path, res);path.remove(path.size() - 1);}}
}

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:res = []def backtrack(start, path, total):if len(path) == k:if total == n:res.append(path.copy())returnfor i in range(start, 10):if total + i > n:breakif 9 - i < k - len(path) - 1:breakpath.append(i)backtrack(i+1, path, total+i)path.pop()backtrack(1, [], 0)return res

五、总结与优化

1. 算法对比

方法	优势	适用场景
回溯法	精准剪枝，避免无效搜索	中等规模组合问题
迭代法	无递归栈溢出风险	极大k值情况
位运算	空间效率高	小规模组合枚举