Leetcode-括号匹配，深度分析与思考

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
分析：
这是道训练递归，准确的说是回溯，非常好的题。对于递归或者回溯不太熟练的朋友来说，看到最后的输出结果时，可能不知道如何下手去实现递归，最后的输出结果非常的完美，没有任何差错，实际在到达完美的那一步前做了很多过滤和判断。
先来回想下这题与 斐波那契数列（FB） 有和不同？

• FB的每一个位置的结果（可能性），仅仅只有一种情况，即 [前一位+前两位] ，所有FB是不涉及回溯的，只需计算出 f(n-1) 和 f(n-2) ，然后一直算到底即可。
• 对于本题来说，本质还是 FB的思想（其实很多题的本质思想都是FB），仔细观察最后的结果会发现每个位置有两种可能性，'(' 或 ')'。那如何让程序帮我们去依次尝试每个位置的两种可能性呢？

如果只进行一次递归，每次只尝试 '(' 或 ')' ，这是肯定不行的， 最后的结果肯定只是 '((((((' 或者 '))))))' 这种形式。出现这种情况，就自然而然的想到用回溯了。
总结： 对于类似这种递归或者回溯的题，或者更难一点的题，第一反应就是去思考 能不能 从“万物的起源”——斐波那契数列 身上找出共性，斐波那契数列不仅仅是一道简答的题，当你刷到了一定的题量，再回来反复看斐波那契数列时会逐渐体会到，它实际上是一个很好的 递归模型，不然我们也不会入手的时候就先学它。。

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return ans;
    }
    
    void dfs(int n, int left, int right, String s) {
        //左右括号必须成对出现才有意义
        if(left == n && right == n) {
            ans.add(s);
            return ;
        }
        //如果左括号的个数小于n，则可以使用
        if(left < n) {
            //与斐波那契数列表面不一样，一个 +1 一个 -1， 本质不还是一样，层层尝试
            dfs(n, left + 1, right, s + "(");
        }
        if(left > right) {
            //第二个递归就真正的 体现出来了 [回溯]
            //因为每个位置有两种可能，总的 有来有回  的去判断，去尝试
            dfs(n, left, right + 1, s +")");
        }
    }
}