力扣22 - 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

var parenthesis = [String]()

func generateParenthesis(_ n: Int) -> [String] {
    generate(0, 0, n, "")
    return parenthesis
}

func generate(_ left: Int, _ right: Int, _ n: Int, _ s: String) {
    
    if left == n && right == n {
        parenthesis.append(s)
        return
    }
    
    if left < n {
        generate(left + 1, right, n, s + "(")
    }
    
    if left > right {
        generate(left, right + 1, n, s + ")")
    }
}

//["((()))", "(()())", "(())()", "()(())", "()()()"]
generateParenthesis(3)