面试题 08.09. 括号

题干

括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。

说明：解集不能包含重复的子集。

例如，给出 n = 3，生成结果为：

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/bracket-lcci

 

思路

约束条件

1.结束条件

当左括号数量=右括号数量=n，结束并记录该方案

2.什么时候匹配失败

当右括号数量>左括号的数量时，匹配失败

3.不能选左括号，只能选右括号

当左括号数量=n时，不能再选左括号了

4.不能选右括号，只能选左括号

当右括号数量=左括号数量

5.剩下的情况是左右括号都能选

 

代码

class Solution {
    int n;
    ArrayList<String> res=new ArrayList<>();//记录答案
    public List<String> generateParenthesis(int n) {
        this.n=n;//括号对数
        int left=0;//左括号的个数
        int right=0;//右括号的个数
        dfs(0,0,"");
        return res;
    }
    private void dfs(int left,int right,String str){
        if(left==n&&right==left) {//当左括号数量=右括号数量=n
            res.add(str);//结束并记录该方案
            return;//返回
        }
        //不能选右括号，只能选左括号：当右括号数量=左括号数量，且左括号数量<n
        if(left+1<=n&&left==right) {
            dfs(left+1,right,str+"(");
        }
        //不能选左括号，只能选右括号，当左括号数量=n时，不能再选左括号了
        else if(left==n) {
            dfs(left,right+1,str+")");
        }
        //剩下的情况左右括号都能选
        else {
            dfs(left+1,right,str+"(");
            dfs(left,right+1,str+")");
        }
    }
}

结果