How does backtracking work in this "Generate Parentheses" question?

Question

I put the code below in a debugger and saw that for a base case of n=2 when the function reaches line 7, the return statement, it goes back and pops the last 3 parentheses. Why is this, I thought that the return statement is supposed to exit the function?

stack = []
res = []
n=2
def backtrack(openN, closedN):
  if openN == closedN ==n:
     res.append("".join(stack))
     return

  if openN < n:
     stack.append("(")
     backtrack(openN+1, closedN)
     stack.pop()

  if closedN < openN:
     stack.append(")")
     backtrack(openN, closedN+1)
     stack.pop()

backtrack(0,0)
print(res)

The result is : ['(())', '()()']

Answer 1

It is instructive to add debug print statements to trace through the operation.

We call generateParenthesis. That calls backtrack, with the default parameter S = []. We get to the second if, append a ( and call backtrack again. That takes the same path, and calls backtrack again. Now the call stack is:

generateParenthesis
  backtrack([], 0, 0)
    backtrac(['('], 1, 0)
      backtrack(['(','('], 2, 0)

This time, left is not less than n, so we take the third if. We append a right paren and call backtrack again. That takes the same path, so we end up with:

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)
        backtrack(['(','(',')'], 2, 1)
          backtrack(['(','(',')',')'], 2, 2)

At this point, len(S) == 2 * n is true, so we take the first option. We append to the ans list and return, but that only returns from that innermost call.

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)
        backtrack(['(','(',')'], 2, 1)

That call was left in the middle of the third if. It pops from S and returns, leaving us with

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)

and so on, until the final call returns.