广西网站建设哪里好毕业设计模板范文

广西网站建设哪里好,毕业设计模板范文,深圳设计公司推荐,wordpress去除分类目录 一、题目 1#xff1a;组合#xff08;LeetCode 77#xff09; 题目描述 核心思路 难点 重点 Java 实现#xff08;带剪枝#xff09; 拓展延伸 二、题目 2#xff1a;组合总和 III#xff08;LeetCode 216#xff09; 题目描述 核心思路 难点 组合LeetCode 77题目描述核心思路难点 重点Java 实现带剪枝拓展延伸二、题目 2组合总和 IIILeetCode 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控制枚举起点重点剪枝逻辑减少无效递归比如n4,k2时start1的枚举上限是 3不用枚举到 4。Java 实现带剪枝class Solution { public ListListInteger combine(int n, int k) { ListListInteger result new ArrayList(); ListInteger 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, ListInteger current, ListListInteger 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); // 下一个数从i1开始 current.removeLast(); // 回溯撤销选i } } }拓展延伸类似题目子集LeetCode 78组合的变种选任意个数的组合去掉current.size() k的终止条件即可组合总和LeetCode 39允许重复选元素只需将i1改为i。二、题目 2组合总和 IIILeetCode 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 ListListInteger combinationSum3(int k, int n) { ListListInteger result new ArrayList(); ListInteger 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, ListInteger current, ListListInteger 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(); // 回溯 } } }拓展延伸类似题目组合总和 IILeetCode 40数组有重复元素需先排序 跳过重复元素第 k 小的和LeetCode 373组合和的 TopK 问题可结合优先队列优化。三、题目 3括号生成LeetCode 22题目描述给定数字n生成所有有效的括号组合左括号数 右括号数任意前缀左括号数≥右括号数。核心思路回溯法选括号 有效性约束选择分支从 “选数字” 变为 “选左 / 右括号”通过约束保证有效性左括号数left n时可选左括号右括号数right left时可选右括号利用字符串不可变性实现自动回溯不用手动删字符。难点 重点难点有效性约束的转化左≤n、右≤左重点字符串不可变的自动回溯简化代码。Java 实现极简版 剪枝class Solution { public ListString generateParenthesis(int n) { ListString result new ArrayList(); backtrack(n, 0, 0, , result); return result; } // left已用左括号数right已用右括号数current当前括号串 private void backtrack(int n, int left, int right, String current, ListString 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组合总和 III216括号生成22回溯核心选数字无重复选数字无重复 和约束选括号有效性约束选择分支多分支枚举数字用 for 循环多分支枚举数字用 for 循环双分支选左 / 右括号用 if 判断约束条件选 k 个数、不重复选选 k 个数、和为 n、数字 1-9 不重复左≤n、右≤左、总长度 2n回溯方式手动 removeLastList手动 removeLastList自动回溯字符串不可变剪枝策略剩余数字够凑 k 个剩余数字够凑 k 个 和不超 target剩余位置够补右括号 可成对笔记总结这三题是回溯法的经典应用核心逻辑都是「选分支→递归→回溯」差异仅在于选择分支的数量和约束条件的类型当选择分支是 “多个候选值”如选数字用for循环枚举当选择分支是 “固定操作”如选括号用if判断剪枝的本质是提前终止无效分支需结合题目的约束条件设计。