Leetcode 22. Generate Parentheses

Problem

Leetcode 22 - Generate Parentheses

Example:

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

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

Approach

We can use a recursive algorithm and make DFS to get the result

• if number of openN == closeN == n, then we want to append result with string
• if number of openN < n, then we append open bracket then recursively start with openN+1
• if number of closeN < openN, then we append closed bracket then recursively start with closeN+1

Visualization of the Approach:

n = 3      Each number represents (openN, closeN)
                       (0, 0)
                         |
                       (1, 0)
                     /       \
                (2,0)         (1,1)
                /  \             \
            (3,0)  (2,1)          (2,1)
            /      /  \           /   \
        (3,1)   (3,1) (2,2)     (3,1) (2,2)
        /       /      /        /      /
    (3,2)     (3,2)  (3,2)    (3,2)  (3,2)
    /         /       /       /       /
(3,3)       (3,3)   (3,3)   (3,3)   (3,3)

Here is the Python code for the solution:

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

        def backTrack(openN, closeN):
            if openN == closeN == n:
                res.append(''.join(stack))
                return
            
            if openN < n:
                stack.append('(')
                backTrack(openN+1, closeN)
                stack.pop()
            
            if closeN < openN:
                stack.append(')')
                backTrack(openN, closeN+1)
                stack.pop()
        
        backTrack(0, 0)
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(2^2n)$

Space Complexity: $O(n)$