题目描述
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
思路
尝试把问题缩减为子问题。
如果现在有了 n
对括号,那么我们想生成 n+1
对括号的话,需要把括号放在哪里呢?
尝试从 0 开始枚举:
- 0:
[]
- 1:
[()]
对于两对括号的情况,它要么包裹第一对括号,要么放在第一对括号的外面:
- 2:
[(()),()()]
那么考虑有多种括号的情况呢?
我们其实可以将括号分成三个部分:假设一共有 n
个括号,我们想新添加一个括号,将剩下 n-1
个括号分成 p
和 q
,并且我们有一个 dp[i]
的数组,保存了从 0 到 n-1
的括号组合。
那么我们 dp[n]
的元素一定是 ({e_p}){e_q}
,其中 e_p
和 e_q
是 dp[p]
和 dp[q]
中的元素。
那么这样我们就可以一层一层地构造 dp 数组,最后返回 dp[n]
。
最终代码:
想得太多
- p 的范围处理的有点问题,因为 python 右边界取不到 i,因此 p 的最大值就是 i-1。因此 range 边界不需要设置为 i-1。
- 为什么只有
({e_p}){e_q}
一种情况呢?感觉可以用反证法证明。