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

LeetCode 77/216/22组合型回溯法-组合 / 组合总和 III / 括号生成） - 详解

news 2026/5/12 10:34:21

一、题目 1：组合（LeetCode 77）

题目描述

核心思路

难点 & 重点

Java 实现（带剪枝）

拓展延伸

二、题目 2：组合总和 III（LeetCode 216）

题目描述

核心思路

难点 & 重点

Java 实现（带双重剪枝）

拓展延伸

三、题目 3：括号生成（LeetCode 22）

题目描述

核心思路

难点 & 重点

Java 实现（极简版 + 剪枝）

拓展延伸

四、三题对比（回溯法的共性与差异）

笔记总结

一、题目 1：组合（LeetCode 77）

题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合（组合无顺序，元素不重复选）。

核心思路

回溯法（选数 + 剪枝）：

用current记录当前选择的组合，result存最终结果；
从start开始枚举数字（避免重复组合，比如选了 1 就不回头选 0）；
终止条件：current.size() == k，将当前组合加入结果；
剪枝优化：枚举时限制i的上限为n - (k - current.size()) + 1（剩余数字不够凑k个时直接终止）。

难点 & 重点

难点：避免重复组合（通过start控制枚举起点）；
重点：剪枝逻辑（减少无效递归，比如n=4,k=2时，start=1的枚举上限是 3，不用枚举到 4）。

Java 实现（带剪枝）

class Solution {public List> combine(int n, int k) {List> result = new ArrayList<>();List current = new ArrayList<>();if (n < k) return result; // 特殊情况：n不够选k个backtrack(n, 1, k, current, result);return result;}// start：当前枚举的起始数字；need：还需选的数字个数private void backtrack(int n, int start, int k, List current, List> result) {// 终止：凑够k个数if (current.size() == k) {result.add(new ArrayList<>(current)); // 注意new新列表，避免引用污染return;}int need = k - current.size();int maxI = n - need + 1; // 剪枝：i的上限for (int i = start; i <= maxI; i++) {current.add(i);       // 选ibacktrack(n, i + 1, k, current, result); // 下一个数从i+1开始current.removeLast(); // 回溯：撤销选i}}
}

拓展延伸

类似题目：
- 子集（LeetCode 78）：组合的变种（选任意个数的组合），去掉current.size() == k的终止条件即可；
- 组合总和（LeetCode 39）：允许重复选元素，只需将i+1改为i。

二、题目 2：组合总和 III（LeetCode 216）

题目描述

找出所有相加之和为 n 的 k 个数的组合，满足：仅用数字 1-9、每个数字最多用一次，返回所有有效组合。

核心思路

回溯法（选数 + 和约束 + 剪枝）：在 “组合” 题的基础上，增加和的约束：

用sum记录当前组合的和；
终止条件：current.size() == k且sum == n；
额外剪枝：sum + i > n时直接终止（后续数字更大，和会超）。

难点 & 重点

难点：同时满足 “选 k 个数”“和为 n”“数字 1-9 不重复” 三个约束；
重点：和的剪枝（sum + i > n），避免无效递归。

Java 实现（带双重剪枝）

class Solution {public List> combinationSum3(int k, int n) {List> result = new ArrayList<>();List current = new ArrayList<>();backtrack(k, n, 1, 0, current, result);return result;}// start：枚举起点；sum：当前组合的和private void backtrack(int k, int target, int start, int sum, List current, List> result) {// 终止：凑够k个数且和为targetif (current.size() == k) {if (sum == target) {result.add(new ArrayList<>(current));}return;}int need = k - current.size();int maxI = 9 - need + 1; // 剪枝1：剩余数字够凑k个for (int i = start; i <= maxI; i++) {// 剪枝2：当前和+当前数超过target，后续数更大，直接终止if (sum + i > target) break;current.add(i);backtrack(k, target, i + 1, sum + i, current, result);current.removeLast(); // 回溯}}
}

拓展延伸

类似题目：
- 组合总和 II（LeetCode 40）：数组有重复元素，需先排序 + 跳过重复元素；
- 第 k 小的和（LeetCode 373）：组合和的 TopK 问题，可结合优先队列优化。

三、题目 3：括号生成（LeetCode 22）

题目描述

给定数字n，生成所有有效的括号组合（左括号数 = 右括号数，任意前缀左括号数≥右括号数）。

核心思路

回溯法（选括号 + 有效性约束）：选择分支从 “选数字” 变为 “选左 / 右括号”，通过约束保证有效性：

左括号数left < n时，可选左括号；
右括号数right < left时，可选右括号；
利用字符串不可变性实现自动回溯（不用手动删字符）。

难点 & 重点

难点：有效性约束的转化（左≤n、右≤左）；
重点：字符串不可变的自动回溯（简化代码）。

Java 实现（极简版 + 剪枝）

class Solution {public List generateParenthesis(int n) {List result = new ArrayList<>();backtrack(n, 0, 0, "", result);return result;}// left：已用左括号数；right：已用右括号数；current：当前括号串private void backtrack(int n, int left, int right, String current, List result) {// 剪枝：提前终止无效分支int remain = 2 * n - current.length(); // 剩余位置int diff = left - right; // 左-右的数量差if (remain < diff || (remain - diff) % 2 != 0) {return; // 剩余位置不够补右括号，或无法成对}// 终止：凑够n对括号if (current.length() == 2 * n) {result.add(current);return;}// 选左括号if (left < n) {backtrack(n, left + 1, right, current + '(', result);}// 选右括号if (right < left) {backtrack(n, left, right + 1, current + ')', result);}}
}

拓展延伸

类似题目：
- 不同括号类型（LeetCode 20）：验证括号有效性（基础）；
- 生成所有有效括号（LeetCode 22 变种）：支持{}/[]/()，需用栈记录匹配关系。

四、三题对比（回溯法的共性与差异）

维度	组合（77）	组合总和 III（216）	括号生成（22）
回溯核心	选数字（无重复）	选数字（无重复 + 和约束）	选括号（有效性约束）
选择分支	多分支（枚举数字，用 for 循环）	多分支（枚举数字，用 for 循环）	双分支（选左 / 右括号，用 if 判断）
约束条件	选 k 个数、不重复选	选 k 个数、和为 n、数字 1-9 不重复	左≤n、右≤左、总长度 2n
回溯方式	手动 removeLast（List）	手动 removeLast（List）	自动回溯（字符串不可变）
剪枝策略	剩余数字够凑 k 个	剩余数字够凑 k 个 + 和不超 target	剩余位置够补右括号 + 可成对