22. 括号生成

22. 括号生成

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

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

提示：
1 <= n <= 8

思路：

考虑使用 DFS( Depth-first search 深度优先搜索) 来解决此类问题，很多排列组合相关的问题，都可以通过DFS来解决 ；但要注意括号规则的推理，什么时候可以选择左括号 什么时候可以选择右括号，不能出现无效组合

复杂度分析.png

class Solution {

    public List<String> generateParenthesis(int n) {
      
      //0.边界处理
      List<String> list = new ArrayList();
      if(n < 0) return list;

      //1.定义需要的数据结构
      char[] cs = new char[n<<1];//左移一位是因为 5对括号有10个半括号
      
      //2.dfs
      dfs(list,n,n,cs,0);

      //3.返回结果
      return list;
    
    }
    
    /**
     DFS:深度优先搜索
     @param: list 存放结果数组
     @param: leftRemain 左括号剩余数量
     @param: rigthRemain 右侧括号数量
     @param: cs 每次组装后得到的字符数组
     @param: idx 搜索的层号
     */
    private void dfs(List<String> list,int leftRemain,int rigthRemain, char[] cs,int idx) {

        //1.结束条件: 到最后一层
        if(idx==cs.length) {
           list.add(new String(cs));
            return;
        }

        //2.枚举这一层所有的选择(什么时候可以添加左括号? 什么时候可以添加右括号) 添加到cs中保存 
        //注意：下面的两种情况是 平行关系 两种选择而已
        //2.1 只要还有左括号就可以添加，说明还有括号没完全配对 leftRemain > 0
        if(leftRemain > 0) {
            cs[idx] = '(';
            dfs(list,leftRemain-1,rigthRemain,cs,idx+1);
        }

        //2.2 还有括号 且 剩余左括号数量跟右括号数量不相等 rightRemain > 0 && leftRemain != rightRemain
        if(rigthRemain > 0 && leftRemain != rigthRemain) {
            cs[idx] = ')';
            dfs(list,leftRemain,rigthRemain-1,cs,idx+1);
        }

    }
    
}

执行结果.png