import java.util.*;

/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 *
 * https://leetcode-cn.com/problems/generate-parentheses/description/
 *
 * algorithms
 * Medium (72.27%)
 * Likes:    600
 * Dislikes: 0
 * Total Accepted:    51.9K
 * Total Submissions: 71.8K
 * Testcase Example:  '3'
 *
 * 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
 * 
 * 例如，给出 n = 3，生成结果为：
 * 
 * [
 * ⁠ "((()))",
 * ⁠ "(()())",
 * ⁠ "(())()",
 * ⁠ "()(())",
 * ⁠ "()()()"
 * ]
 * 
 * 
 */

// @lc code=start

/**
 * 方法1：深度优先遍历
 */

 /*
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        if(n == 0) return list;

        dfs("", n, n, list);
        return list;
    }

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

        //两种if就相当于之前for遍历每层的节点
        //注意不要写成ifelse 要是并列的；两个if 相当于for的两种情况
        //所谓隐式回溯 就是每次if都是传入的新值 因此不用像for中的push/pop
        if(left > 0){ //其实不写两个大于零的条件也可以 
            dfs(res + "(", left-1, right, list);
        }

        if(right > 0 && left < right){
            dfs(res + ")", left, right-1, list);
        }
    }
}
*/


/**
 * 方法2：广度优先遍历 
 * 对每一层的两种情况（左边加括号/右边加括号）进行处理
 * 结果保存在最后的队列中 
 */

 /*
class Solution{
    
    class Node{
    private String res;
    private int left;
    private int right;

    public Node(String res, int left, int right){
        this.res = res;
        this.left = left;
        this.right = right;
    }
}
    public List<String> generateParenthesis(int n) {
        //创建队列用于存储每一层的节点
        Queue<Node> queue = new LinkedList<>();
        //空字符串作为root节点先放入队列
        queue.offer(new Node("", n, n));

        //每一层拼凑上一个字符 总的字符数是2*n 隐层要循环2*n次
        n = 2*n;
        while(n > 0){
            int size = queue.size();
            //将队列中的每个节点拿出来处理
            //就是上层的节点
            for(int i = 0; i < size; i++){
                Node curNode = queue.poll();
                //两种情况
                if(curNode.left > 0){
                    queue.offer(new Node(curNode.res + "(", curNode.left-1, curNode.right));
                }
                if(curNode.right > 0 && curNode.left < curNode.right){
                    queue.offer(new Node(curNode.res + ")", curNode.left, curNode.right-1));
                }
            }
            n--;
        }

        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()){
            list.add(queue.poll().res);
        }
        
        return list;
    }
} 
*/

/**
 * 方法3：动态规划
 * 基本思想：动态规划就是根据i<n的已知信息，根据算法推出i=n时的情况
 * 本题：i=n相比于i=n-1多了一个括号，将之前的情况分别放在该新括号的左右
 * "(" + <i=p时所有括号的排列组合> + ")" + <i=q时所有括号的排列组合>
 * 
 */

class Solution{
    public List<String> generateParenthesis(int N) {
        //存放每种情况下的List
        List<List<String>> list = new ArrayList<>();

        //初始条件
        list.add(new ArrayList<String>(Arrays.asList("")));
        list.add(new ArrayList<String>(Arrays.asList("()")));

        for(int n = 2; n <= N; n++){
            List<String> temp = new ArrayList<>();
            //遍历pq组合，如(0,2) (1,1) (2,0)
            for(int p = 0; p <= n-1; p++){
                int q = n-1-p;
                //分别遍历pq各自的可能进行组合
                List<String> pList = list.get(p);
                List<String> qList = list.get(q);
                for (String pStr : pList) {
                    for (String qStr : qList) {
                        String res = "(" + pStr + ")" + qStr;
                        temp.add(res);
                    }
                }
            }
            list.add(temp);
        }

        return list.get(N);
    }
}

// @lc code=end