Generate Parentheses (Leetcode #22)

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Answer:

This is one of my favorite questions since it is the first time we encounter backtracking. The question becomes much easier when we draw a decision tree

On the left side of the tree, we add an open bracket until it is equal to the constraints. And on the left side of each node, we add a closing bracket only if when there are open bracket.

Personally, for me, I find the logic to be quite simple, the most challenging part for me is the coding.

What is backtracking?

A problem-solving algorithmic technique that find solution incrementally by trying different options and undo them if they lead to a dead end.

How Does Backtracking Algorithm Work?

1. Choose an initial solution

2. Explore all possible extensions of the current solution

3. If an extension leads to a solution return that solution

4. If it doesn't lead to a solution then backtrack to a previous solution and try a different extension

5. repeat step 2-4 until we get the answer

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n: #step 1
                res.append("".join(stack)) #step 3
            if openN < n: #step 2
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop() #step 4
            if closedN < openN: #step 2
                stack.append(")")
                backtrack(openN , closedN + 1)
                stack.pop() #step 4

        backtrack(0,0)
        return res