leedcode:括号生成

4.9日：括号生成

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

示例：

• 输入：n=3

• 输出：[

  ? “((()))”,

  ? “(()())”,

  ? “(())()”,

  ? “()(())”,

  ? “()()()”

  ? ]

class Solution{
    List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n){
    dfs(n,n,"");return res;}private void dfs(int left,int right,String curStr){
    //左右括号都不剩余了，终止递归if(left == 0 && right == 0){
    res.add(curStr);return;}//如果左括号还有剩余的话，可以拼接左括号if(left > 0){
    dfs(left - 1,right,curStr + "(");}//如果右括号剩余多余左括号剩余的话，可以拼接右括号if(right > left){
    dfs(left,right - 1,curStr + ")");}}
}