打印 n 对括号的所有有效组合的算法

我正在解决问题陈述中提出的问题。我知道我的解决方案是正确的（运行程序），但我很好奇我是否正确分析了我的代码（如下）。

def parens(num)
  return ["()"] if num == 1
  paren_arr = []
  parens(num-1).each do |paren| 
    paren_arr << paren + "()" unless "()#{paren}" == "#{paren}()"
    paren_arr << "()#{paren}"
    paren_arr << "(#{paren})"
  end
  paren_arr
end

例如，parens(3) 将输出以下内容：

["()()()", "(()())", "(())()", "()(())", "((()))"]

这是我的分析： 每个 f(n) 值的元素数量大约是 f(n-1) 的 3 倍。所以：

f(n) = 3 * f(n-1) = 3 * 3 * f(n-2) ~ (3^n) 时间成本。 通过类似的分析，堆栈将被 f(1)..f(n) 占用，因此空间复杂度应该为 3^n。

我不确定这种时间或空间的分析是否正确。一方面，堆栈仅保存 n 个函数调用，但每个调用都返回一个数组，其大小约为之前调用的 3 倍。这会影响空间成本吗？我的时间分析正确吗？

正如其他人提到的，您的解决方案不正确。

对于这个问题，我最喜欢的解决方案是通过重复地将当前字符串递增到词法上的下一个有效组合来生成所有有效组合。

“Lexically next”分为几个规则，使其变得非常简单：

• 字符串中的第一个差异将“(”更改为“)”。否则，下一个字符串在词法上将位于当前字符串之前。

• 第一个差异是尽可能向右。否则增量会更小。

• 第一个差异之后的部分在词汇上是最小的，同样是因为否则会有更小的增量。在这种情况下，这意味着所有“(”都位于所有“)”之前。

因此，您所要做的就是找到最右边可以更改为“)”的“(”，将其翻转，然后附加正确数量的“(”和“)”。

我不懂 Ruby，但在 Python 中它看起来像这样：

current="(((())))"
while True:
    print(current)
    opens=0
    closes=0
    pos=0
    for i in range(len(current)-1,-1,-1):
        if current[i]==')':
            closes+=1
        else:
            opens+=1
            if closes > opens:
                pos=i
                break
    if pos<1:
        break
    current = current[:pos]+ ")" + "("*opens + ")"*(closes-1)

Output:

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

事实证明，对于许多类型的“生成所有组合”问题，这样的解决方案既简单又快速。