知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 组合总和 ## 题目(LeetCode 39) > 💬 **Q:我这段代码哪里错了?** > > 把代码格式化后看,有一个关键 bug:**`break` 的前提是数组已排序,但你没有排序。** > > ```java > if (target < candidates[i]) { > break; // ← 这里假设数组是升序的,后面的数都更大,可以直接跳出 > } > ``` > > 如果 `candidates = [3, 1, 2]`,`target = 2`: > - `i=0`:`candidates[0]=3 > 2`,直接 break > - 结果:`[1,2]` 和 `[2]` 都没找到,答案错误 > > **修复:在开头加一行排序:** > > ```java > Arrays.sort(candidates); // 加这一行,break 才能正确工作 > ``` > > 排序后 `break` 才成立——当前数已经超过 target,后面的数只会更大,可以安全跳出。 > > 你注释掉的 `if (target < 0) return` 是另一种思路,两种不能混用: > > ``` > 思路 A(排序 + break):先排序,遇到 candidates[i] > target 直接 break > 思路 B(不排序 + continue):不排序,遇到 candidates[i] > target 用 continue 跳过,target < 0 时 return > ``` > > 你的代码是思路 A 的框架,加上 `Arrays.sort(candidates)` 就完全正确了。 给定一个无重复元素的数组 candidates 和一个目标值 target,找出所有和为 target 的组合。每个数字可以无限次使用。 ``` 输入:candidates = [2, 3, 6, 7], target = 7 输出:[[2, 2, 3], [7]] ``` ## 大白话理解 你有几种面额的硬币(可以无限用),凑出目标金额的所有方式。 和子集问题的区别: - 子集:选不选 - 组合总和:选几个(可以重复选) ## 决策树 ``` target = 7, candidates = [2, 3, 6, 7] 剩余=7 / / \ \ 选2 选3 选6 选7 剩余=5 剩余=4 剩余=1 剩余=0 ✓ → [7] / | \ / \ 选2 选3 选6 选3 选6 剩余=3 ... 剩余=1 / \ 选2 选3 剩余=1 剩余=0 ✓ → [2,2,3] | 选2 剩余=-1 ✗ 超了,剪枝 ``` ## 代码 ```java class Solution { private List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); // 排序,方便剪枝 backtrack(candidates, target, 0, new ArrayList<>()); return result; } private void backtrack(int[] candidates, int remain, int startIndex, List<Integer> path) { if (remain == 0) { result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < candidates.length; i++) { // 剪枝:如果当前数已经大于剩余值,后面的更大,直接跳出 if (candidates[i] > remain) break; path.add(candidates[i]); // 注意:可以重复选,所以下一轮还是从 i 开始(不是 i+1) backtrack(candidates, remain - candidates[i], i, path); path.remove(path.size() - 1); } } } ``` ### 关键点 ``` 可以重复选 → backtrack(..., i, ...) 从 i 开始 不能重复选 → backtrack(..., i + 1, ...) 从 i+1 开始 这一个参数的区别,决定了元素能不能重复使用 ``` ### 剪枝为什么有效? ``` 排序后 candidates = [2, 3, 6, 7] 如果 remain = 4,当遍历到 6 时: 6 > 4,不可能凑出来 7 > 4,也不可能 → 直接 break,不用继续了 没有排序就不能 break,只能 continue(效率差很多) ``` ## 变体:组合总和 II(LeetCode 40)— 每个数只能用一次,有重复元素 ``` 输入:candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 输出:[[1,1,6], [1,2,5], [1,7], [2,6]] ``` ```java private void backtrack(int[] candidates, int remain, int startIndex, List<Integer> path) { if (remain == 0) { result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < candidates.length; i++) { if (candidates[i] > remain) break; // 同一层去重 if (i > startIndex && candidates[i] == candidates[i - 1]) continue; path.add(candidates[i]); backtrack(candidates, remain - candidates[i], i + 1, path); // i+1,不能重复用 path.remove(path.size() - 1); } } ``` 两处变化: 1. `i + 1`:每个元素只能用一次 2. 同层去重:`i > startIndex && nums[i] == nums[i-1]` ## 变体:组合(LeetCode 77)— 从 1~n 中选 k 个数 ``` 输入:n = 4, k = 2 输出:[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]] ``` ```java private void backtrack(int n, int k, int startIndex, List<Integer> path) { if (path.size() == k) { result.add(new ArrayList<>(path)); return; } // 剪枝:剩余的数不够凑 k 个了 for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { path.add(i); backtrack(n, k, i + 1, path); path.remove(path.size() - 1); } } ``` ## 复杂度 - 时间:取决于解的数量,最坏指数级 - 空间:O(target / min(candidates)),递归深度 ## 一句话总结 组合总和 = 子集模板 + remain 计数 + 排序剪枝。可重复选从 i 开始,不可重复选从 i+1 开始。 --- 上一篇:[03 - 子集](./03-subsets.md) | 下一篇:[05 - 电话号码的字母组合](./05-letter-combinations.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入