【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);
        }
    }
}

原文地址：https://blog.csdn.net/passer__jw767/article/details/143619414

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！