22. Generate Parentheses

Medium LeetCode

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

How to solve the problem

• Backtracking (DFS)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        m = n * 2  # Total length of the result string
        result = []
        path = [''] * m  # Temporary path for current parenthesis sequence

        # i: current position in path
        # open: number of '(' used so far
        def dfs(i, open):
            # If we've used up all positions, add to result
            if i == m:
                result.append(''.join(path))
                return
            # If we can still add '(', do so
            if open < n:
                path[i] = '('
                dfs(i + 1, open + 1)
            # If number of ')' used so far < number of '(' used, we can add ')'
            if i - open < open:
                path[i] = ')'
                dfs(i + 1, open)

        dfs(0, 0)
        return result

Complexity

• Time complexity: O(K*C(n, k))
• Space complexity: O(K*C(n, k))