LC 22 - Generate Parentheses

Question

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

Links

Question here and solution here

Solution

concept

The main concept here is backtracking. We have 3 conditions to follow:

1. when the number of open and close bracket is equal to n, thats our base case and we return the answer
2. we can add open brackets as much as we want, but never exceed n
3. number of close bracket < number of open bracket

code

class Solution:
	"""
	using stack
	we need to pop the stack everytime we are done adding since it is a global variable
	"""
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        stack = []

        def backtrack(open_bracket_num, close_bracket_num):
            if open_bracket_num == close_bracket_num == n:
                ans.append("".join(stack))
                return

            if open_bracket_num < n:
                stack.append("(")
                backtrack(open_bracket_num + 1, close_bracket_num)
                stack.pop()
            
            if close_bracket_num < open_bracket_num:
                stack.append(")")
                backtrack(open_bracket_num, close_bracket_num + 1)
                stack.pop()
                
        backtrack(0,0)
        return ans

class Solution:
	"""
	use string as path
	note that we do not need to pop since `path` is local variable
	"""
    def generateParenthesis(self, n: int) -> List[str]:
            res = []
            def backtrack(open_n, closed_n, path):
                if open_n == closed_n == n:
                    res.append(path)
                    return

                if open_n < n:
                    backtrack(open_n + 1, closed_n, path + "(")

                if closed_n < open_n:
                    backtrack(open_n, closed_n + 1, path + ")")
                    
            backtrack(0, 0, "")
            return res

Complexity

time: $O(\frac{4^n}{\sqrt{n}})$
space: $O(n)$