求问各位大佬，这个代码里面left的值什么时候减小了？

kking1

def generateParenthesis(n: int) -> list[str]:
    ans = []
    def backtrack(S, left, right):
        if len(S) == 2 * n:
            ans.append(''.join(S))
            return
        if left < n:
            S.append('(')
            print(S)
            print (left)
            backtrack(S, left+1, right)
            print (left)
            S.pop()
            print(S)
        if right < left:
            S.append(')')
            print(S)
            backtrack(S, left, right+1)
            S.pop()
            print(S)
    backtrack([], 0, 0)
    return ans

print(generateParenthesis(2))

Twilight6

left 没有减小，只有增大，即递归时传入 left + 1 时，此次的递归过程相比之前增大 1

代码中没有对 left 直接或间接的减小操作，因此 left 参数不可能自己减小

kking1

Twilight6 发表于 2022-8-21 13:22
left 没有减小，只有增大，即递归时传入 left + 1 时，此次的递归过程相比之前增大 1

代码中没有对  ...

['(']
0
['(', '(']
1
['(', '(', ')']
['(', '(', ')', ')']
['(', '(', ')']
['(', '(']
1
['(']
['(', ')']
['(', ')', '(']
1
['(', ')', '(', ')']
['(', ')', '(']
1
['(', ')']
['(']
0
[]
['(())', '()()']
这是运行出来得结果，left有 从1到0的过程，我也看着只有增大，不知道后面怎么又出现0了

Twilight6

kking1 发表于 2022-8-25 12:26
['(']
0
['(', '(']

这是递归，不同时刻的递归过程，你传入的 left 值不同，打印出来的自然也不同，两次打印的 left 不是同一个 left

backtrack([], 0, 0) --> if left < n  --> print(left) 此时输出 0 之后进入递归 --> 而 backtrack([], left + 1, right) 即 backtrack([], 0 + 1, 0)

backtrack([], 1, 0) -->  if left < n  --> print(left) 此时输出 1 之后进入递归 --> 而 backtrack([], left + 1, right) 即 backtrack([], 1 + 1, 0)

后续递归返回同理，输出：

1

0