题目描述

• 先吐槽：括号题好恶心。。
• 括号有效判断需要考虑考虑
  

代码 & 解法

• 思路：把括号分开看，这道题和20.有效的括号其实是有差别的：这道题的括号是成对的，而20题的括号则没有这个硬性要求。
  基于此，我们可以用这么一个思路去考虑这道题：分配一个大小为2n的括号集，其中n个是左括号，n个是右括号
• 递归过程中需要剪枝，递归结束时获得答案。
• 结果正确性：见代码注释1.2.

class Solution {
    public List<String> generateParenthesis(int n) {
        /**
            1. 如何确保不重复：画格子，走不同分枝肯定至少有一个格子不同。如下
            	    [x][x][o][x]
            	    [x][x][o][o]
               也就是无论如何，不同分枝代表的字符串内容肯定不相同。
            2. 如何跑全：因为包括了所有左右括号组合。
        */

        ArrayList<String> ans = new ArrayList<>();
        dfs(ans, n, n, "");
        return ans;
    }

    // ans（存储答案）；left（左括号剩余数）；right（右括号剩余数）；now（当前字符串）
    public void dfs(ArrayList<String> ans, int left, int right, String now) {
        // 递归结束
        if (left == 0 && right == 0) {
            ans.add(now);
        }
        // 剪枝情况：如")"，肯定是错误顺序。
        if (right < left) {
            return;
        }
        // 走左括号路线
        if(left > 0){
            dfs(ans, left - 1, right, now + "(");
        }
        // 走右括号路线
        if(right > 0){
            dfs(ans, left, right - 1, now + ")");
        }
        return;
    }
}