生成括号结果时的额外值

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

不同之处在于，在您的版本中，局部变量

openN

在当前调用框架内发生了变化：

openN -= 1

而ChatGPT的版本，它仅作为递归调用参数进行更改：

# ChatGPT -- correct

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

在您的版本中，

if

结构是这样的，在给定的帧中，在顶部

openN -= 1

中执行

if

将影响底部

openN

中使用的

if

值，使其比应有的值少1是：

# 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)

但如果顶部分支运行，您的调用就会关闭 1，从而使

openN

减少 1 并破坏当前帧其余部分的值。

不仅如此，在正确版本中，保护底部递归调用的条件过去是

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

在突变后从未使用过。但它仍然是糟糕的风格，因为如果您决定在重构或功能更改后使用它，它很容易在将来导致错误，因此最佳实践是不要改变它。

如果您不喜欢参数列表中带有减法和加法的“繁忙”递归函数调用，您可以为当前值创建新变量。如果这些值是非原始值（不是这里的情况），请小心正确复制。

另一个一般提示：打印值或使用调试器来查看两个版本之间的差异。在

print(closeN, openN)

条件上方添加

if closeN > openN:

可以明确其中一个差异。

Answer 2

当回溯函数结束执行时，它会继续执行父函数。 对于您的代码，当您执行generateParanthesis(1)时，在第一次执行时您会得到：

堆栈=[]

第0步回溯(1,1,'')

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

第 1 步回溯(0,1,'(')

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

第2步回溯(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 的回溯步骤。

这就是为什么你的列表中有 2 个“()”。

ChatGPT 所做的并不是改变当前步骤中变量的值，而只是将不同的值发送到下一步。这样，当你返回到第0步时，你仍然有openN = 1和closeN = 1，并且你不会进入最后一个if

Answer 3

在

backtrack

内部，您正在按顺序检查两个条件。因此，如果您在递归函数调用之外递减 

if openN > 0:

，则 

if closeN > openN:

 和 

openN -= 1

 可能在一次运行中都为 true。

请注意，第二个条件必须按顺序排列，仅将第二个

if

 更改为 

elif

 将破坏递归的逻辑。

因此，为了避免这个问题，只需在函数调用内部递减并在一次迭代期间保持变量的值不变！