生成括号结果中的额外值

Question

def generateParenthesis(n):
    stack = []
    def backtrack(openN, closeN, s):
        if closeN == 0:
            stack.append(s)
            return
        if openN > 0:
            s += '('
            openN -= 1
            backtrack(openN, closeN, s)
        if closeN > openN:
            s += ')'
            closeN -= 1
            backtrack(openN, closeN, s)   
    backtrack(n,n,'')
    return stack
print(generateParenthesis(3))

输出结果是

['((()))', '((()))', '(()())', '(()())', '()(())', '()(())', '()()()', '()()()']

但我期望的结果是

['((()))', '(()())', '(())()', '()(())', '()()()']

为什么会有重复的值呢？

def generateParenthesis(n):
    stack = []

    def backtrack(openN, closeN, s):
        # If no more closing parentheses are needed, add the sequence to the stack
        if closeN == 0:
            stack.append(s)
            return
        # If there are open parentheses to add, add one and recurse
        if openN > 0:
            backtrack(openN - 1, closeN, s + '(')
        # If the number of closing parentheses needed is greater than the number of opening ones,
        # it's safe to add a closing parenthesis and recurse
        if closeN > openN:
            backtrack(openN, closeN - 1, s + ')')

    # Start the recursive process with the full count of opening and closing parentheses
    backtrack(n, n, "")
    return stack

# Example usage
print(generateParenthesis(3))

这是ChatGPT的结果。我觉得这个代码的操作和我的一样。但我不知道为什么结果会不一样。

Answer 1

在 backtrack 函数里，你依次检查了两个条件。所以如果你在递归函数调用之外把 openN 减少1，那么这两个条件 if openN > 0: 和 if closeN > openN: 在一次运行中都有可能同时为真。

要注意，第二个条件必须按顺序检查，如果把第二个 if 改成 elif，那么递归的逻辑就会出问题。

为了避免这个问题，建议在函数调用内部进行减法操作，并且在一次迭代中保持变量的值不变！

Answer 2

当你的回溯函数执行完毕后，它会继续执行它的父函数。对于你的代码，当你执行generateParanthesis(1)时，第一次执行的情况是：

栈 = []

步骤 0 backtrack(1,1,'')

openN = 1, closeN = 1
you enter in the if openN > 0
s becomes '('
openN = 0, closeN = 1

步骤 1 backtrack(0,1,'(')

you enter in the if closeN > openN:
s becomes '()'
openN = 0, closeN = 0

步骤 2 backtrack(0,0,'()')

You enter if closeN == 0
stack = ['()']
step2 ends

返回到步骤 1，之前的if是最后一个命令，步骤 1结束。

返回到步骤 0:

current state: 
s = '('
openN = 0, closeN = 1

we continue executing and we enter in closeN > openN:
openN = 0, closeN = 0
s = '()'

然后你再做一步类似于步骤 2 的回溯。

这就是为什么你的列表中有两个'()'的原因。

ChatGPT所做的并不是改变当前步骤中变量的值，而是将不同的值传递到下一步。这样，当你返回到步骤 0 时，openN = 1 和 closeN = 1，最后的if不会被执行。

Answer 3

你们的代码版本有个区别，就是你那里的局部变量 openN 在当前的调用框架中被修改了：openN -= 1，而 ChatGPT 的版本只是把它当作递归调用的参数来改变。

# ChatGPT -- correct

# ...
if openN > 0:
   backtrack(openN - 1, closeN, s + '(')
#            ^^^^^^^^^
# ...

在你那段代码中，if 结构是这样的：在某个框架中，如果在最上面的 if 里执行了 openN -= 1，那么下面的 if 使用的 openN 值就会变得比它应该的少一。

# Your version -- incorrect

# ...
if openN > 0:
    s += '('
    openN -= 1  # change openN
    backtrack(openN, closeN, s)
if closeN > openN:  # this condition is now less strict by 1
    s += ')'
    closeN -= 1
    backtrack(openN, closeN, s)  # call backtrack(openN - 1, closeN - 1, s)
# ...

简单来说，我们想要的调用是 backtrack(openN, closeN - 1, s)，但如果上面的分支执行了，你的代码就会少减一，导致 openN 的值在当前框架中被搞错了。

而且，保护下面递归调用的条件在正确的版本中是 if closeN > openN:，而在你那里的版本变成了 if closeN > openN - 1:。这个条件更容易满足，这样就会产生额外的结果（更多的递归调用意味着输出结果更多）。

这里的一个基本原则是：除非有充分的理由，否则不要修改值。每个递归调用框架都应该仅仅基于它的参数来计算。如果这些参数在局部被修改了，特别是在 if 语句中，逻辑就很容易变得混乱，导致你计算的结果是针对不同的调用框架，或者在这种情况下，进行一个对算法没有意义的递归调用（打开和关闭的计数需要和 s 保持同步）。

很多编程语言不允许修改值，或者有些语言让你更容易把参数值声明为常量。在 C++ 中写成 void backtrack(const int openN, const int closeN, const std::string &s) 会让逻辑更安全，避免在编译时出现不必要的 -= 操作。

需要注意的是，closeN -= 1 技术上并不是个错误，因为在修改后 closeN 不会再被使用。但这仍然是个不好的风格，因为如果你在重构或功能改变后决定使用它，就很容易引发错误，所以最佳实践是不要去修改它。

如果你不喜欢在参数列表中进行加减的“繁忙”递归函数调用，可以为当前值创建新变量。只要小心，如果这些值不是基本类型（在这里不是这种情况），要正确复制。

另一个小建议是：打印值或者使用调试工具来查看两个版本之间的差异。在 if closeN > openN: 条件上方添加 print(closeN, openN) 可以清楚地显示出其中一个差异。