Recursion Question with Valid Parenthesis

Question

I am trying to understand this solution for generating all valid parentheses.

The part I don't understand is how the recursion can find ALL of the different combinations. When I debug through the code, I put a watch on the integers "left" and "right." With the input of 2 in generateParenthesis, after "ans" is populated with 1 valid parenthesis, at "return ans" I see the variable "right" decrease making the if statement "right < left" valid. How does the variable "right" decrease like that when I never specifically set it to do so? To put it simply, how is recursion able to find all the cases of valid parenthesis, not just one in this situation?

Below I included the question along with an online Python Debugger to see what I'm talking about. https://onlinegdb.com/LMNYtq3iR

https://leetcode.com/problems/generate-parentheses/

def generateParenthesis(N):
   ans = []
   S = ''
   left = 0
   right = 0
   ans = backtrack(N, S, left, right, ans)

def backtrack(N, S, left, right, ans):
   print(left)
   if len(S) == 2 * N:
      ans.append(S)
   if left < N:
      backtrack(N, S+'(', left+1, right, ans)
   if right < left:
    backtrack(N, S+')', left, right+1, ans)

   return ans
    
generateParenthesis(2)

Answer 1

The variable right does never decrease. You see the value of an earlier recursive execution. It may become clearer if you include the current recursion level in the output:

print(" "*len(S), S, left, right)

  0 0
  ( 1 0
   (( 2 0
    (() 2 1
     (()) 2 2
   () 1 1   <-- left and right do not decrease, this is the call after `( 1 0` above
    ()( 2 1
     ()() 2 2

On an unrelated note, you are using return inconsistently here. The backtrack function does not have to return at all, since it adds elements to the ans parameter, and the generateParenthesis does not return at all. I'd suggest dropping the ans parameter and changing the function to be a proper generator function instead:

def generateParenthesis(N):
   return backtrack(N, S="", left=0, right=0)

def backtrack(N, S, left, right):
   print(" "*len(S), S, left, right)
   if len(S) == 2 * N:
       yield S
   if left < N:
       yield from backtrack(N, S+'(', left+1, right)
   if right < left:
       yield from backtrack(N, S+')', left, right+1)
    
print(list(generateParenthesis(2)))