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: ["()"]

Solution

Intuition

We can implement a back-tracking solution here. The way we need to think about this is, for example given n = 3:

• You can have 3 open bracket and 3 close bracket in total. Now it's up to you where to put them.
• At 1 stage, you can:
  • Put a ( if numberOfOpenBracket < 3
  • Put a ) if numberOfOpenBracket > numberOfCloseBracket.

Therefore, we can have this following tree presentation

Implementation

class App:
    def generateParentheses(self, n: int) -> List[str]:
        self.n = n
        self.result = []
        self._generateParentheses(0, 0, "")
        return self.result

    def _generateParentheses(self, openBracketCount, closeBracketCount, parentheses):
        if openBracketCount == closeBracketCount == self.n:
            self.result.append(parentheses)

        if openBracketCount < self.n:
            self._generateParentheses(openBracketCount + 1, closeBracketCount, parentheses + "(")
        if openBracketCount > closeBracketCount:
            self._generateParentheses(openBracketCount, closeBracketCount + 1, parentheses + ")")

Time complexity: $O(2^{2n})$

• At each iteration we have 2 choices — open or close the bracket
• The bracket comes with pairs, therefore if we have n pairs of bracket we have 2n in total

Space complexity: $O(2^{2n})$

• Because of the way we're using recursion, it's the same.