Generate Parentheses (in Python)

Problem

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

For example, given n=3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

Approach 1 : Brute Force

Complexity Analysis

•Time Complexity : \(O(2^{2n}*n)\). For each of \(O(2^{2n})\) sequences, we need to create and validate the sequence, which takes \(O(n)\) work.

•Space Complexity : \(O(2^(2n)*n). Naively, every sequence could be valid.

---

Approach 2 : Backtracking

class Solution(object):
    def generateParenthesis(self, N):
        ans = []
        def backtrack(S = '', left = 0, right = 0):
            if len(S) == 2 * N:
                ans.append(S)
                return
            if left < N:
                backtrack(S+'(', left+1, right)
            if right < left:
                backtrack(S+')', left, right+1)
 
        backtrack()
        return ans

• Time Complexity : $O(\dfrac{4^n}{\sqrt{n}})$. Each valid sequence has at most n steps during the backtracking procedure.

• Space Complexity : $O(\dfrac{4^n}{\sqrt{n}})$, as described above, and using $O(n)$ space to store the sequence. 

Source

https://leetcode.com/problems/generate-parentheses/