【LeetCode】【算法】22. 括号生成

LeetCode 22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思路

天天到处看答案，看的灵神的解题思路回溯不会写？套路在此！（Python/Java/C++/Go/JS），只能感叹我自己能力有限，看答案也要瞅半天（主要非常容易走神。。。）

1. 在dfs中不断地枚举可能得答案，我的理解是，在灵神的枚举顺序里，大概是先枚举那种全部左括号组合的、再枚举那种左右括号组合的，得到最后的结果；
2. 对于枚举方法，传入的参数是目前填的括号总数i和目前的左括号个数open
3. 一开始写终止条件：if(i==n*2)，也就是括号个数满足要求了，就存答案，return;
4. 接下来，第一步先放左括号if(open<n)，在这里边不断地递归每填一个左括号的结果
5. 上面递归放完了所有左括号后，再考虑左右括号配对的解法，于是通过if(i-open<open)的方式来填写右括号

代码

class Solution {private int n; // 括号对数，也就是左括号的最大个数private final List<String> ans = new ArrayList<>();private char[] path;public List<String> 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);}}
}