Python: Solving "Generate Parentheses" with Backtracking --> Confused About stack.pop()

Question

I am trying to understand the backtracking code below:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        stack = []
        res = []

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

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

        backtrack(0, 0)
        return res

I am having a hard time conceptually grasping where the stack.pop() is hitting. For example, in the screen shot below how does the code get from the top yellow highlight to the bottom yellow highlight?

How is the code able to pop off three ")" without needing to append them back?

Answer 1

The code is recursive, it traverses the tree and the traversal is constrained by some invariants:

• The number of open braces can never exceed n
• The number of closed braces can never exceed the number of open braces

Therefore, you have up to two potential possibilities to look into at every step:

• adding an open braces
• adding a closed brace

In addition to this, after exhausting all valid suffixes for a given prefix all you can do is pop another brace off the stack to check if there are any unaccounted suffixes left for this shorter prefix.

For example, you can start by adding ( and ). Then, you'll consider all possible combinations of n-1 pairs. Then, you'll "go back" and pop off the first ) leaving it open until the end.

This is called backtracking. It's just a fancy term for going back up the tree you are traversing.

I suggest you print the stack every time you add or remove a brace to better understand the stages of the traversal:

def generateParenthesis(n):

    stack = []
    res = []

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

        if openN < n:
            stack.append("(")
            print ("openN < n; +:", stack)
            backtrack(openN + 1, closedN)
            stack.pop()
            print ("openN < n; -:", stack)
        if closedN < openN:
            stack.append(")")
            print ("closedN < openN, +:", stack)
            backtrack(openN, closedN + 1)
            stack.pop()
            print ("closedN < openN, -:", stack)
    backtrack(0, 0)
    return res

Now let's go through the output:

openN < n; +: ['(']
openN < n; +: ['(', '(']
openN < n; +: ['(', '(', '(']
closedN < openN, +: ['(', '(', '(', ')']
closedN < openN, +: ['(', '(', '(', ')', ')']
closedN < openN, +: ['(', '(', '(', ')', ')', ')']
closedN < openN, -: ['(', '(', '(', ')', ')']
closedN < openN, -: ['(', '(', '(', ')']
closedN < openN, -: ['(', '(', '(']
openN < n; -: ['(', '(']
closedN < openN, +: ['(', '(', ')']
openN < n; +: ['(', '(', ')', '(']
closedN < openN, +: ['(', '(', ')', '(', ')']
closedN < openN, +: ['(', '(', ')', '(', ')', ')']
closedN < openN, -: ['(', '(', ')', '(', ')']
closedN < openN, -: ['(', '(', ')', '(']
openN < n; -: ['(', '(', ')']
closedN < openN, +: ['(', '(', ')', ')']
openN < n; +: ['(', '(', ')', ')', '(']
closedN < openN, +: ['(', '(', ')', ')', '(', ')']
closedN < openN, -: ['(', '(', ')', ')', '(']
openN < n; -: ['(', '(', ')', ')']
closedN < openN, -: ['(', '(', ')']
closedN < openN, -: ['(', '(']
openN < n; -: ['(']
closedN < openN, +: ['(', ')']
openN < n; +: ['(', ')', '(']
openN < n; +: ['(', ')', '(', '(']
closedN < openN, +: ['(', ')', '(', '(', ')']
closedN < openN, +: ['(', ')', '(', '(', ')', ')']
closedN < openN, -: ['(', ')', '(', '(', ')']
closedN < openN, -: ['(', ')', '(', '(']
openN < n; -: ['(', ')', '(']
closedN < openN, +: ['(', ')', '(', ')']
openN < n; +: ['(', ')', '(', ')', '(']
closedN < openN, +: ['(', ')', '(', ')', '(', ')']
closedN < openN, -: ['(', ')', '(', ')', '(']
openN < n; -: ['(', ')', '(', ')']
closedN < openN, -: ['(', ')', '(']
openN < n; -: ['(', ')']
closedN < openN, -: ['(']
openN < n; -: []
['((()))', '(()())', '(())()', '()(())', '()()()']

It's true that when you remove ) for the first time you continue by removing the other two. You must because before trying any other arrangement you have to remove at least one open brace.

If you follow the trace closely, you'll see that you remove as many braces as you need to in order to remove an open brace you have not removed until now.

Hopefully that helps, let me know if I can clarify this further.