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

Question

我正在研究问题陈述中陈述的问题.我知道我的解决方案是正确的(运行程序),但我很好奇我是否正确分析我的代码(下面).

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倍.这会影响太空成本吗？我的时间分析是否正确？

Answer 1

正如其他人所说,你的解决方案是不正确的.

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

"Lexually next"分解为一些规则,使其变得非常简单:

• 字符串中的第一个区别是'('变为'')'.否则,下一个字符串将在当前字符串之前有词法.

• 第一个区别是尽可能向右.否则会有较小的增量.

• 第一个差异之后的部分是词法上最小的,再次因为否则会有较小的增量.在这种情况下,这意味着所有'('在所有'之前')'.

因此,您所要做的就是找到最右边的'('可以更改为')',翻转它,然后附加正确数量的'('s和').

我不懂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)

输出:

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

对于许多类型的"生成所有组合"问题,这样的解决方案变得简单快速.