iOS LeetCode☞括号生成-爱代码爱编程

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

示例：

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

题解：
为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n-1 的序列前加一个 ‘(’ 或 ‘)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的。

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

如果左括号数量不大于 nn，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。

代码：

    func generateParenthesis(_ n: Int) -> [String] {
        func backtrack(ans: inout [String], cur: String, open: Int, close: Int, max: Int) -> Void {
            var curStr = cur;
            if curStr.count == max * 2 {
                ans.append(curStr);
                return;
            }
            if open < max {
                curStr.append("(");
                backtrack(ans: &ans, cur: curStr, open: open + 1, close: close, max: max);
                curStr.removeLast();
            }
            if close < open {
                curStr.append(")");
                backtrack(ans: &ans, cur: curStr, open: open, close: close + 1, max: max);
                curStr.removeLast();
            }
        }
        var ans = [String]();
        backtrack(ans: &ans, cur: "", open: 0, close: 0, max: n);
        return ans;
    }