括号生成题目链接https://leetcode.cn/problems/generate-parentheses/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public ListString generateParenthesis(int n) { ListString ans new ArrayList(); backtreack(n, 0, 0, new StringBuffer(), ans); return ans; } //left左括号的个数 right右括号的个数 public void backtreack(int n, int left, int right, StringBuffer output, ListString ans){ if(right n){ ans.add(output.toString()); return; } if(left 1 n){ //选取左括号 left; output.append((); backtreack(n, left, right, output, ans); //回溯 left--; output.deleteCharAt(output.length()-1); } if(right 1 left){ //选取右括号 right; output.append()); backtreack(n, left, right, output, ans); //回溯 right--; output.deleteCharAt(output.length()-1); } }分析代码的时间复杂度计算复杂详情请参考官方解析方法二中的时间复杂度分析空间复杂度为O(n)。解题思路采用递归 回溯方法思路简单故不赘述。看了官方题解后的解答//方法一暴力法(思路简单效率低故直接粘贴了官方的解答) //时间复杂度O(n*2^2n)对于2^2n个序列中的每一个我们用于建立和验证该序列的复杂度为 O(n)。 //空间复杂度O(n) public ListString generateParenthesis(int n) { ListString combinations new ArrayListString(); generateAll(new char[2 * n], 0, combinations); return combinations; } public void generateAll(char[] current, int pos, ListString result) { if (pos current.length) { if (valid(current)) { result.add(new String(current)); } } else { current[pos] (; generateAll(current, pos 1, result); current[pos] ); generateAll(current, pos 1, result); } } public boolean valid(char[] current) { int balance 0; for (char c: current) { if (c () { balance; } else { --balance; } if (balance 0) { return false; } } return balance 0; } //方法二回溯法此方法与我的解答一致但我参考官方解答将我的解答略微优化了一些多于的步骤 //时间复杂度本方法的时间复杂度计算复杂详情请参考官方解析 //空间复杂度O(n) public ListString generateParenthesis(int n) { ListString ans new ArrayList(); backtreack(n, 0, 0, new StringBuffer(), ans); return ans; } //left左括号的个数 right右括号的个数 public void backtreack(int n, int left, int right, StringBuffer output, ListString ans){ if(right n){ ans.add(output.toString()); return; } if(left n){ //选取左括号 output.append((); backtreack(n, left1, right, output, ans); //回溯 output.deleteCharAt(output.length() - 1); } if(right left){ //选取右括号 output.append()); backtreack(n, left, right1, output, ans); //回溯 output.deleteCharAt(output.length() - 1); } } //方法三按括号序列的长度递归 //本方法的时间复杂度和空间复杂度计算复杂详情请参考官方解析 ArrayList[] cache new ArrayList[9]; public ListString generateParenthesis(int n) { return generate(n); } public ListString generate(int n){ if(cache[n] ! null){ return cache[n]; } ArrayListString res new ArrayList(); if(n 0){ res.add(); } else{ for(int i0; in; i){ for(String left : generate(i)){ for(String right : generate(n-1-i)){ res.add(( left ) right); } } } } cache[n] res; return res; }分析 1、方法一采用暴力枚举每次对枚举出的结果进行验证若是有效答案则加入结果。 2、方法二在方法一的基础上进行了优化递归前先通过左括号和右括号的个数进行判断保证递归的答案一定是有效的。 3、方法三的解题思路对于每一个有效的括号序列一定是以(“开头以”)结尾的所以每一个有效的括号序列都是 (a)b 的形式其中a和b既可以为空也可以是有效的括号序列。经过以上分析我们只需递归计算 a 的所有可能和 b 的所有可能遍历 a 与 b 的所有可能性并拼接即可得到所有长度为 2n 的括号序列。另外为了节省计算时间我们可以在每次 generate(i) 函数返回之前把返回值存储起来下次再调用 generate(i) 时可以直接返回不需要再递归计算。总结本题只需掌握基本的递归与回溯即可。对于本题的方法三我们需要善于观察与总结关键在于“对于每一个有效的括号序列一定是以(“开头以”)结尾的所以每一个有效的括号序列都是 (a)b 的形式其中a和b既可以为空也可以是有效的括号序列”这个结论在这个结论的基础上可以很轻松的得出“a、b可能性拼接”的解题方法。
