22. 括号生成

题目链接：https://leetcode-cn.com/problems/generate-parentheses/

思路：

1. 「暴力求解法」。比如n为3，那么返回的一个字符串的长度应该为2*n，即为6。等价于我们要在6个「格子」中填充，每个「格子」有两种选择。（ '(' 或者 ')' ），这样的话时间复杂度为O（2^2n）。

2. 「剪枝法」。在「暴力求解法」的基础上，增加一些「validate」，可以删去很多的操作。
   比如：

• 局部字符串，判断是否有效，第一个字符填充')'，则不必考虑之后「格子」填充的情况。
• n个括号，则最多有n个左括号和n个右括号，我们记录左括号使用数left，和有括号使用数right。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let list = [];
    __gen__(0, 0, n, '');
    return list;

    function __gen__(left, right, n, result) {

        // 终止条件，left和right都用完了，那么就把当前的result放入list数组中
        if(left === n && right === n) {
            list.push(result);
            return;
        }

        // 添加左括号的条件，只有left个数小于总数n即可
        if(left < n) {
            __gen__(left + 1, right, n, result + '(');
        }

        // 添加有括号的条件，不仅仅是right个数小于总数n，而且不能大于left个数。
        if(right < n && right < left) {
            __gen__(left, right + 1, n,result + ')');
        }
        
    }
};