- 正确答案：组合总和 II 要求在给定一个候选数组 candidates 和一个目标数 target 的情况下，找出所有使得数字和为 target 的组合，其中每个数字在 candidates 中只能使用一次，且结果中不能包含重复的组合。解决该问题的核心是使用回溯算法，并结合排序与剪枝来去重。 - 解答思路： 1. 首先对 candidates 数组进行排序，便于后续剪枝和去重。 2. 使用回溯法遍历所有可能的组合路径，在每一步选择一个数字加入当前路径。 3. 由于每个数字只能使用一次，递归时从下一个索引开始。 4. 去重关键：在同一层递归中，如果当前数字与前一个数字相同，则跳过，避免生成重复组合。注意：这是“树层去重”，不是“树枝去重”。 5. 剪枝优化：如果当前数字加入后超过 target，由于数组已排序，后续更大的数也必然超过，可以直接 break。 - 深度知识讲解：本题考察的核心知识点包括： 1. 回溯算法（Backtracking）： - 回溯是暴力搜索的一种优化形式，通过“路径记录 + 选择与撤销”机制，系统地枚举所有可能解。 - 通常用于组合、排列、子集等问题。 - 回溯模板结构如下： - 终止条件（当前路径和等于 target） - 循环遍历选择列表 - 剪枝条件（如当前和已超过 target） - 选择当前元素，加入路径 - 递归处理下一层 - 撤销选择（回溯） 2. 去重机制（重点）： - 为什么排序后可以去重？因为相同元素相邻，便于判断是否重复使用。 - 去重逻辑：在 for 循环中（即同一树层），若当前元素与前一个元素相同且前一个未被使用（或前一个在同一层已被处理），则跳过。 - 关键判断：`i > start && candidates[i] == candidates[i-1]` 表示不是第一个元素，且与前一个相同，则跳过。 - 注意：这里不需要额外的 visited 数组来标记是否使用，因为我们是按索引顺序递增使用的，且每个数只用一次。 3. 剪枝优化： - 排序后，若当前 candidates[i] 已使路径和超过 target，则 break，因为后面的数更大。 - 这种剪枝显著减少搜索空间，提升效率。 4. 数据结构： - 使用 List path 存储当前路径。 - 使用 List> result 存储所有合法组合。 - 参数传递中需注意递归调用时的索引控制（start）以避免重复使用元素。 - 代码示例（Java 风格伪代码）： ``` public List> combinationSum2(int[] candidates, int target) { List> result = new ArrayList<>(); List path = new ArrayList<>(); Arrays.sort(candidates); // 排序以便去重和剪枝 backtrack(candidates, target, 0, path, result); return result; } private void backtrack(int[] candidates, int target, int start, List path, List> result) { if (target == 0) { result.add(new ArrayList<>(path)); // 找到一个有效组合 return; } for (int i = start; i < candidates.length; i++) { // 剪枝：当前数已大于剩余目标值 if (candidates[i] > target) break; // 去重：跳过同一层中重复的数字 if (i > start && candidates[i] == candidates[i-1]) continue; path.add(candidates[i]); // 选择 // 递归下一层，从 i+1 开始，每个数只能用一次 backtrack(candidates, target - candidates[i], i + 1, path, result); path.remove(path.size() - 1); // 撤销选择 } } ``` - 扩展知识： 1. 与 LC39（组合总和 I）的区别： - LC39 允许重复使用同一元素，因此递归时 start 不变； - LC40 每个元素只能用一次，递归时 start = i + 1。 - LC39 不需要去重（输入无重复），LC40 需要处理输入中的重复元素。 2. 回溯算法的时间复杂度分析： - 最坏情况：O(2^n)，因为每个元素可选或不选。 - 实际由于剪枝和去重，远小于理论值。 - 空间复杂度：O(target / min(candidates))，即递归深度，最坏为 target 最小值的商。 3. 应用场景： - 组合优化问题，如零钱兑换变种、背包问题的组合输出。 - 在金融、资源分配等领域中用于枚举可行解。 4. 相关变种题： - LC47：全排列 II（同样需要去重） - LC90：子集 II - 这些题目共同构成“回溯 + 去重”经典题型族。总结：LC40 组合总和 II 是一道典型的回溯算法题，重点在于理解“树层去重”的逻辑，掌握排序 + 剪枝 + 回溯三者结合的编程范式。面试中常被用来考察候选人对递归深度控制、重复处理和算法优化的综合能力。

百度提前批一面面经

全站热榜

创作者周榜