22. 括号生成

题意：

解题思路：

思路：
    1. 递归左右括号；
    2. 每次新增左括号的数目不能超过n；
    3. 每次新增右括号的数目不能超过n，并且左括号要大于右括号的数量；

PHP代码实现：

class Solution {
    public $list = [];
    function generateParenthesis($n) {
        $this->generate(0, 0, $n, "");
        return $this->list;
    }
    function generate($left, $right, $n, $s) {
        if ($left == $n && $right == $n) {
            $this->list[] = $s;
            return;
        }
        if ($left < $n) $this->generate($left + 1, $right, $n, $s. "(");
        if ($right < $n && $left > $right) $this->generate($left, $right + 1, $n, $s. ")");
    }
}

GO代码实现：

func generateParenthesis(n int) []string {
    result := make([]string, 0)
    generate("", 0, 0, n, &result)
    return result
}
func generate(current string, left, right, n int, result *[]string) {
    if left == n && right == n {
        *result = append(*result, current)
        return
    }
    if left < n {
        generate(current + "(", left + 1, right, n, result)
    }
    if right < n && left > right {
        generate(current + ")", left, right + 1, n, result)
    }
}