Python中的递归问题，输出有重复值

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

当回溯函数结束执行时，它会继续执行父函数。 对于您的代码，当您执行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 2

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

closeN

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

closeN -= 1

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

#         vvvvvvvvv
backtrack(openN - 1, closeN, s + '(')

在您的版本中，

if

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

openN -= 1

中执行

if

将影响底部

openN

中使用的

if

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

# ...
if openN > 0:
    s += '('
    openN -= 1  # change openN
    backtrack(openN, closeN, s)
if closeN > openN:
    s += ')'
    closeN -= 1
    backtrack(openN, closeN, s)  # call backtrack(openN - 1, closeN - 1, s)`
# ...

在底线上，我们想要的调用是

backtrack(openN, closeN - 1, s)

，但如果顶部分支运行，你的调用就会减少 1，从而使 

openN

 减少 1，并且基本上破坏了当前帧的值。

这里的一般经验法则是：除非有充分的理由，否则不要改变值。每个调用帧都需要纯粹根据其参数进行计算。如果这些参数发生变化，特别是在

if

 中，逻辑很容易发生变化，这样您就可以计算不同调用框架的结果，或者在这种情况下，进行对算法没有意义的调用。 

Answer 3

在

backtrack

内部，您正在检查两个彼此独立的条件。因此，如果您在函数调用之外递减 

if openN > 0:

，则 

if closeN > openN:

 和 

openN -= 1

 在一个符文中可能都为 true。

要避免这种行为，只需将第二个

if

更改为

elif

，这样如果满足第一个条件，则不会检查第二个条件！这样，您将获得与按照 ChatGPT 建议在函数调用内递减相同的结果。