旅游网站的规划与建设开题报告,wordpress怎么修改中文字体,合肥建设管理学校网站,网站如何做网页查询LeetCode 22. 括号生成
题目描述
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
解题思路
天天到处看答案#xff0c;看的灵神的解题思路回溯不会写#xff1f;套路在此#xff01;#xff08;Pyth…LeetCode 22. 括号生成
题目描述
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
解题思路
天天到处看答案看的灵神的解题思路回溯不会写套路在此Python/Java/C/Go/JS只能感叹我自己能力有限看答案也要瞅半天主要非常容易走神。。。
在dfs中不断地枚举可能得答案我的理解是在灵神的枚举顺序里大概是先枚举那种全部左括号组合的、再枚举那种左右括号组合的得到最后的结果对于枚举方法传入的参数是目前填的括号总数i和目前的左括号个数open一开始写终止条件if(in*2)也就是括号个数满足要求了就存答案return;接下来第一步先放左括号if(openn)在这里边不断地递归每填一个左括号的结果上面递归放完了所有左括号后再考虑左右括号配对的解法于是通过if(i-openopen)的方式来填写右括号
代码
class Solution {private int n; // 括号对数也就是左括号的最大个数private final ListString ans new ArrayList();private char[] path;public ListString generateParenthesis(int n) {this.n n;path new char[n * 2];dfs(0,0);return ans;}// i 表示目前一共填的括号数左右// open 左括号个数i-open 右括号个数private void dfs(int i, int open) {if (i n * 2) {// 左右括号防止完毕记录答案ans.add(new String(path));return ;}if (open n){ // 当前还可以放左括号path[i] (;dfs(i 1, open 1); // 总括号数量1左括号数量1}if (i - open open){ // 如果左括号放不了就该放右括号了path[i] );dfs(i 1, open);}}
}
