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

目录

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

题目描述

核心思路

难点 & 重点

Java 实现（带剪枝）

拓展延伸

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

题目描述

核心思路

难点 & 重点

Java 实现（带双重剪枝）

拓展延伸

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

题目描述

核心思路

难点 & 重点

Java 实现（极简版 + 剪枝）

拓展延伸

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

笔记总结

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

题目描述

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

核心思路

回溯法（选数 + 剪枝）：

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

难点 & 重点

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

Java 实现（带剪枝）

class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); List<Integer> 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<Integer> current, List<List<Integer>> 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); // 选i backtrack(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、每个数字最多用一次，返回所有有效组合。

核心思路

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

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

难点 & 重点

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

Java 实现（带双重剪枝）

class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); List<Integer> 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<Integer> current, List<List<Integer>> result) { // 终止：凑够k个数且和为target if (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，生成所有有效的括号组合（左括号数 = 右括号数，任意前缀左括号数≥右括号数）。

核心思路

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

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

难点 & 重点

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

Java 实现（极简版 + 剪枝）

class Solution { public List<String> generateParenthesis(int n) { List<String> 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<String> 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 变种）：支持{}/[]/()，需用栈记录匹配关系。

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

笔记总结

这三题是回溯法的经典应用，核心逻辑都是「选分支→递归→回溯」，差异仅在于选择分支的数量和约束条件的类型：

• 当选择分支是 “多个候选值”（如选数字），用for循环枚举；
• 当选择分支是 “固定操作”（如选括号），用if判断；
• 剪枝的本质是提前终止无效分支，需结合题目的约束条件设计。

  ---