Generate Parentheses
从左到右读取一串括号时，如果 ) 的数量从未超过 ( 的数量，并且最后两者数量相等，那么这串括号就是合法的。因此，(())() 是合法的，而 ())( 不合法：它的第三个字符试图闭合一个从未打开的括号。
给定一个整数 n，返回所有由 n 个左括号和 n 个右括号组成的合法字符串，并按字典序排序，其中 ( 排在 ) 前面。
函数
- ninteger
- 括号对的数量
- 返回值string-array
- 按字典序排列的所有由 n 对括号组成的格式正确的字符串
约束条件
1 ≤ n ≤ 8- 当
n = 8时，答案中有 1,430 个字符串。
示例
- 输入
- n = 3
- 输出
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- 解释
- 三组配对可以组成 5 个格式正确的字符串。
((()))先打开全部三组，因此排在最前面；()()()每次立即闭合一组，因此排在最后面。
- 输入
- n = 1
- 输出
- ["()"]
- 解释
- 一对括号中有一个格式正确的字符串。另一种排列方式
)(会在任何内容打开之前就先关闭。
进阶
不生成这些字符串，你能统计出由 n 对括号组成的合法字符串有多少个吗？
提示
逐个打开提示，每个都会多透露一点。
从左到右读取字符串，并记录尚未配对的左括号数量。当这个数量降到零以下时，哪里出了问题？
一次添加一个字符来构建字符串。只要添加的
(少于n个，你就可以添加(；只要添加的)少于(，你就可以添加)。这样构建的字符串总能完成。使用两个计数器
opened和closed进行递归。先尝试(分支，再尝试)分支；每次调用返回后移除对应字符，并在字符串长度达到2n时保存该字符串。先尝试(可以让输出保持有序。
题解
长度为 2n 的字符串中，格式正确的很少：当 n = 8 时，65,536 个字符串中只有 1,430 个。按从左到右的顺序构建每个字符串，并且只有当前缀仍然可以补全时才添加字符。两个计数器可以判断这一点，先尝试 ( 再尝试 )，就能让字符串按顺序排列。
构建每个字符串，然后检查它
思路
用 ( 和 ) 填满 2n 个位置，共有 4^n 种组合，然后保留格式正确的字符串。检查字符串时，用一个计数器遍历它：遇到 ( 就加 1，遇到 ) 就减 1。当计数器始终不小于 0，且最后为 0 时，字符串的格式才正确。在每个位置优先放置 (，再放置 )，就能按排序顺序列出这些字符串。
检查每个字符串都需要 O(n) 的时间。对于 n = 8，共有 65,536 个字符串，但只有 1,430 个答案，因此约 98% 的工作都白费了，而且每增加一对括号，工作量就会变为原来的四倍。
算法
- 保留一个包含
2n个字符的缓冲区，以及一个用于存放答案的列表。 fill(pos)：如果pos等于2n，并且缓冲区格式正确，就保存它。- 否则，在
pos处放入(并调用fill(pos + 1)，然后在该处放入)并再次调用它。 - 检查时，每遇到一个
(就加 1，每遇到一个)就减 1。如果余额小于 0，或最终不为 0，就舍弃。 - 调用
fill(0)并返回保存的字符串。
def generateParenthesis(n):
result = []
path = []
def is_balanced(text):
balance = 0
for ch in text:
balance += 1 if ch == "(" else -1
if balance < 0:
return False # a ")" with nothing open to close
return balance == 0
def fill():
if len(path) == 2 * n:
text = "".join(path)
if is_balanced(text):
result.append(text)
return
for ch in "()": # "(" first keeps the output sorted
path.append(ch)
fill()
path.pop()
fill()
return result回溯打开和关闭的计数
思路
把检查移到函数体内。只有当一个前缀使用的 ( 不超过 n 个，且 ) 的数量从未超过 ( 的数量时，它才能扩展成格式正确的字符串。因此，当 opened < n 时，可以添加 (；当 closed < opened 时，可以添加 )。长度达到 2n 时，两种括号的数量都是 n，字符串格式正确，无需再检查。
不会遗漏答案，因为格式正确的字符串的每个前缀都符合这两条规则。也不会浪费分支：对于 n = 2，(( 分支只能连续添加两次闭括号，得到 (())；() 分支只能添加一个左括号和一个右括号，得到 ()()。每个字符串都对应树中的一条路径，因此只会出现一次；而且先遍历 ( 分支，所以输出是有序的。
每个叶节点都是一个答案，因此工作量与输出量成正比：O(4^n / √n)。
算法
- 保留正在构建的字符串和两个计数器
opened和closed，它们的初始值都为 0。 - 如果字符串的长度为
2n，就保存一份副本并返回。 - 如果
opened < n，就添加(，使用opened + 1递归调用，然后将其移除。 - 如果
closed < opened，就添加)，使用closed + 1递归调用，然后将其移除。 - 从空字符串开始，并返回保存的字符串。
def generateParenthesis(n):
result = []
path = []
def backtrack(opened, closed):
if len(path) == 2 * n:
result.append("".join(path))
return
# "(" sorts before ")", so trying it first keeps the output sorted
if opened < n:
path.append("(")
backtrack(opened + 1, closed)
path.pop()
if closed < opened: # only close a pair that is open
path.append(")")
backtrack(opened, closed + 1)
path.pop()
backtrack(0, 0)
return result
易错点和边界情况
- 当
closed < n时允许添加)，而不是检查closed < opened。这样会生成())(，其中有一个右括号没有对应的左括号。 - 只在最后检查括号数量是否相等。这样会接受
)(；每一步的平衡值都必须保持在 0 或以上。 - 先尝试
)，再尝试(。正确的字符串会以相反的顺序生成。 - 对于可变的列表或字符串构建器，保存共享缓冲区，而不是它的副本。这样，每个已保存的答案都会显示同一个缓冲区，而回溯会再次清空它。
- 按一个较小的估值确定固定结果数组的大小。
n = 8时有 1,430 个答案。
常见问题3
生成括号的时间复杂度是多少？
回溯会输出 C(n) = (2n)! / ((n+1)! n!) 个字符串，这就是卡塔兰数，其增长速度约为 4^n / (n^1.5 √π)。构造并复制每个字符串需要 O(n) 时间，因此时间复杂度为 O(4^n / √n)。额外空间复杂度为 O(n)，用于存储当前字符串和调用栈，此外还需要存储输出。
n 对括号可以组成多少个有效的括号字符串？
第 n 个 Catalan 数：当 n 从 1 到 8 时，依次为 1、2、5、14、42、132、429 和 1,430。每个格式正确的字符串都可以拆分为 ( A ) B，其中这个 ) 与第一个 ( 匹配，且 A 和 B 合计有 n - 1 对括号。对 A 的大小求和，就得到 Catalan 递推关系。
生成括号问题可以不用递归解决吗？
是的。用一个栈保存部分状态，每个状态都是一个包含两个计数器的字符串，并按照相同的两条规则扩展每个状态。先压入 ) 对应的扩展，再压入 ( 对应的扩展，这样会先弹出 ( 对应的扩展，输出就会保持有序。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def generateParenthesis(n):
# 在这里编写代码测试 #1
测试 #2
参数
n = 3
预期输出
["((()))", "(()())", "(())()", "()(())", "()()()"]