22. 括号生成(Swift版)

一、题目

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如:

给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

二、解题

使用回溯法，只有在我们知道序列仍然保持有效时才添加 '(' or ')'，而不是像方法一那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。
时间复杂度：参考官方题解

三、代码实现

    class Solution {
        
        func generateParenthesis(_ n: Int) -> [String] {
            var result = [String]()
            generate(n: n, open: 0, close: 0, str: "", result: &result)
            return result
        }
        func generate(n: Int, open: Int, close: Int, str: String, result: inout [String]) {
            if open == n && close == n {
                result.append(str)
                return
            }
            if open < n {
                generate(n: n, open: open + 1, close: close, str: str + "(", result: &result)
            }
            if close < open {
                generate(n: n, open: open, close: close + 1, str: str + ")", result: &result)
            }
        }
    }

Demo地址：github