百度文心大模型 LeetCode 22. 括号生成 Java实现

LeetCode 22. 括号生成 - Java 实现题目描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。输入: n 3 输出: [((())),(()()),(())(),()(()),()()()]解题思路回溯法DFS核心思想在每一步决策中只添加合法的括号 规则 1. 左括号 ( 的数量 n → 可以放左括号 2. 右括号 ) 的数量 左括号 → 可以放右括号 3. 当字符串长度 2*n → 得到一个有效组合加入结果集时间复杂度: O(4ⁿ/√n)第 n 个卡特兰数空间复杂度: O(n)递归栈深度 字符串存储图解过程n 3 / \ ( / \ (( ( → 不合法(右左)剪枝 / \ ((( (() | / \ ((() (()) ()( ← 左括号已用完只能加右 | / \ \ ((()) (())( ()() | | | ((())) (())() ()(()) ... 继续回溯探索所有分支Java 实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();backtrack(result,newStringBuilder(),0,0,n);returnresult;}/** * 回溯法生成有效括号 * * param result 结果集 * param current 当前构建的字符串 * param left 已使用的左括号数量 * param right 已使用的右括号数量 * param n 括号对数 */privatevoidbacktrack(ListStringresult,StringBuildercurrent,intleft,intright,intn){// 终止条件字符串长度达到 2*nif(current.length()2*n){result.add(current.toString());return;}// 剪枝条件1左括号数量 n可以添加左括号if(leftn){current.append(();// 做选择backtrack(result,current,left1,right,n);// 递归current.deleteCharAt(current.length()-1);// 撤销选择}// 剪枝条件2右括号数量 左括号数量可以添加右括号if(rightleft){current.append());// 做选择backtrack(result,current,left,right1,n);// 递归current.deleteCharAt(current.length()-1);// 撤销选择}}}完整可运行代码含测试importjava.util.ArrayList;importjava.util.List;publicclassGenerateParentheses{staticclassSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();backtrack(result,newStringBuilder(),0,0,n);returnresult;}privatevoidbacktrack(ListStringresult,StringBuildercurrent,intleft,intright,intn){if(current.length()2*n){result.add(current.toString());return;}if(leftn){current.append(();backtrack(result,current,left1,right,n);current.deleteCharAt(current.length()-1);}if(rightleft){current.append());backtrack(result,current,left,right1,n);current.deleteCharAt(current.length()-1);}}}// 辅助方法打印结果privatestaticvoidprintResults(intn,ListStringresult){System.out.println(n n共 result.size() 种组合);for(inti0;iresult.size();i){System.out.println( (i1). result.get(i));}System.out.println();}publicstaticvoidmain(String[]args){SolutionsolnewSolution();// 测试用例 1: n 1printResults(1,sol.generateParenthesis(1));// 测试用例 2: n 2printResults(2,sol.generateParenthesis(2));// 测试用例 3: n 3printResults(3,sol.generateParenthesis(3));// 测试用例 4: n 4printResults(4,sol.generateParenthesis(4));}}运行结果n 1共 1 种组合 1. () n 2共 2 种组合 1. (()) 2. ()() n 3共 5 种组合 1. ((())) 2. (()()) 3. (())() 4. ()(()) 5. ()()() n 4共 14 种组合 1. (((()))) 2. ((()())) 3. ((())()) 4. ((()))() 5. (()(())) 6. (()()()) 7. (()())() 8. (())(()) 9. (())()() 10. ()((())) 11. ()(()()) 12. ()(())() 13. ()()(()) 14. ()()()()关键要点总结要点说明回溯三要素选择列表、终止条件、撤销选择剪枝条件1left n时才能加(剪枝条件2right left时才能加)字符串构建使用StringBuilder提高效率避免频繁创建字符串卡特兰数结果数量为第 n 个卡特兰数 Cₙ (2n)!/((n1)!n!)卡特兰数验证n结果数公式 Cₙ (2n)!/((n1)!·n!)0111112223554141454242常见错误对比错误写法问题先暴力生成再验证生成 2²ⁿ 种组合再逐一检查效率极低忘记剪枝right left会产生无效序列如())(用String拼接而非StringBuilder每次拼接创建新对象性能差递归没有终止条件栈溢出暴力法 vs 回溯法对比// ❌ 暴力法生成所有组合再验证效率低不推荐classSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();generateAll(,2*n,result);returnresult;}privatevoidgenerateAll(Stringcurrent,intremain,ListStringresult){if(remain0){if(isValid(current))result.add(current);return;}generateAll(current(,remain-1,result);generateAll(current),remain-1,result);}privatebooleanisValid(Strings){intbalance0;for(charc:s.toCharArray()){balance(c()?1:-1;if(balance0)returnfalse;}returnbalance0;}}// ✅ 回溯法边生成边剪枝推荐// 上面的实现方法生成数量是否剪枝推荐度暴力验证2²ⁿ❌❌ 不推荐回溯剪枝Cₙ卡特兰数✅✅ 推荐递归树直观理解n2 / \ ( / \ (( () ← 右括号已等于左括号不能再加右 / \ \ ((( (() ()) ← 此时 right(1) left(2)仍可加右 ✗ / \ ✗ (left3n, 剪枝) (()) ✓ ()( (长度4, 完成) / \ ()() ✓ ()) ✗LeetCode 22. 括号生成 - Java 实现题目描述数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。输入: n 3 输出: [((())),(()()),(())(),()(()),()()()]解题思路回溯法DFS核心思想在每一步决策中只添加合法的括号 规则 1. 左括号 ( 的数量 n → 可以放左括号 2. 右括号 ) 的数量 左括号 → 可以放右括号 3. 当字符串长度 2*n → 得到一个有效组合加入结果集时间复杂度: O(4ⁿ/√n)第 n 个卡特兰数空间复杂度: O(n)递归栈深度 字符串存储图解过程n 3 / \ ( / \ (( ( → 不合法(右左)剪枝 / \ ((( (() | / \ ((() (()) ()( ← 左括号已用完只能加右 | / \ \ ((()) (())( ()() | | | ((())) (())() ()(()) ... 继续回溯探索所有分支Java 实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();backtrack(result,newStringBuilder(),0,0,n);returnresult;}/** * 回溯法生成有效括号 * * param result 结果集 * param current 当前构建的字符串 * param left 已使用的左括号数量 * param right 已使用的右括号数量 * param n 括号对数 */privatevoidbacktrack(ListStringresult,StringBuildercurrent,intleft,intright,intn){// 终止条件字符串长度达到 2*nif(current.length()2*n){result.add(current.toString());return;}// 剪枝条件1左括号数量 n可以添加左括号if(leftn){current.append(();// 做选择backtrack(result,current,left1,right,n);// 递归current.deleteCharAt(current.length()-1);// 撤销选择}// 剪枝条件2右括号数量 左括号数量可以添加右括号if(rightleft){current.append());// 做选择backtrack(result,current,left,right1,n);// 递归current.deleteCharAt(current.length()-1);// 撤销选择}}}完整可运行代码含测试importjava.util.ArrayList;importjava.util.List;publicclassGenerateParentheses{staticclassSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();backtrack(result,newStringBuilder(),0,0,n);returnresult;}privatevoidbacktrack(ListStringresult,StringBuildercurrent,intleft,intright,intn){if(current.length()2*n){result.add(current.toString());return;}if(leftn){current.append(();backtrack(result,current,left1,right,n);current.deleteCharAt(current.length()-1);}if(rightleft){current.append());backtrack(result,current,left,right1,n);current.deleteCharAt(current.length()-1);}}}// 辅助方法打印结果privatestaticvoidprintResults(intn,ListStringresult){System.out.println(n n共 result.size() 种组合);for(inti0;iresult.size();i){System.out.println( (i1). result.get(i));}System.out.println();}publicstaticvoidmain(String[]args){SolutionsolnewSolution();// 测试用例 1: n 1printResults(1,sol.generateParenthesis(1));// 测试用例 2: n 2printResults(2,sol.generateParenthesis(2));// 测试用例 3: n 3printResults(3,sol.generateParenthesis(3));// 测试用例 4: n 4printResults(4,sol.generateParenthesis(4));}}运行结果n 1共 1 种组合 1. () n 2共 2 种组合 1. (()) 2. ()() n 3共 5 种组合 1. ((())) 2. (()()) 3. (())() 4. ()(()) 5. ()()() n 4共 14 种组合 1. (((()))) 2. ((()())) 3. ((())()) 4. ((()))() 5. (()(())) 6. (()()()) 7. (()())() 8. (())(()) 9. (())()() 10. ()((())) 11. ()(()()) 12. ()(())() 13. ()()(()) 14. ()()()()关键要点总结要点说明回溯三要素选择列表、终止条件、撤销选择剪枝条件1left n时才能加(剪枝条件2right left时才能加)字符串构建使用StringBuilder提高效率避免频繁创建字符串卡特兰数结果数量为第 n 个卡特兰数 Cₙ (2n)!/((n1)!n!)卡特兰数验证n结果数公式 Cₙ (2n)!/((n1)!·n!)0111112223554141454242常见错误对比错误写法问题先暴力生成再验证生成 2²ⁿ 种组合再逐一检查效率极低忘记剪枝right left会产生无效序列如())(用String拼接而非StringBuilder每次拼接创建新对象性能差递归没有终止条件栈溢出暴力法 vs 回溯法对比// ❌ 暴力法生成所有组合再验证效率低不推荐classSolution{publicListStringgenerateParenthesis(intn){ListStringresultnewArrayList();generateAll(,2*n,result);returnresult;}privatevoidgenerateAll(Stringcurrent,intremain,ListStringresult){if(remain0){if(isValid(current))result.add(current);return;}generateAll(current(,remain-1,result);generateAll(current),remain-1,result);}privatebooleanisValid(Strings){intbalance0;for(charc:s.toCharArray()){balance(c()?1:-1;if(balance0)returnfalse;}returnbalance0;}}// ✅ 回溯法边生成边剪枝推荐// 上面的实现方法生成数量是否剪枝推荐度暴力验证2²ⁿ❌❌ 不推荐回溯剪枝Cₙ卡特兰数✅✅ 推荐递归树直观理解n2 / \ ( / \ (( () ← 右括号已等于左括号不能再加右 / \ \ ((( (() ()) ← 此时 right(1) left(2)仍可加右 ✗ / \ ✗ (left3n, 剪枝) (()) ✓ ()( (长度4, 完成) / \ ()() ✓ ()) ✗