hot100-22 括号生成

题目描述

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

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：

输入：n = 1
输出：[“()”]

思路

这一类问题是在一棵隐式的树上求解，可以用深度优先遍历。

• 代码好写，使用递归的方法，直接借助系统栈完成状态的转移；
• 广度优先遍历得自己编写结点类和借助队列。

可以分析出的结论：

• 当前左右括号都有大于 0 个可以使用的时候，才产生分支；
• 产生左分支的时候，只看当前是否还有左括号可以使用；
• 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
• 在左边和右边剩余的括号数都等于 0 的时候结算。

代码

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("",n,n);
        return res;
    }

    private void dfs(String curStr,int left,int right){
        if(left==0 && right==0){
            res.add(curStr);
            return;
        }

        if(left>0){
            dfs(curStr+"(",left-1,right);
        }

        if(right>left){
            dfs(curStr+")",left,right-1);
        }
    }
}