Problem Statement in English

You’re given an integer n. Your task is to generate all combinations of well-formed parentheses consisting of n pairs of parentheses.

Approach

To solve this problem, we can use a backtracking approach.

The function that’s going to generate the combinations will need to track 3 parameters – the number of complete pairs of parentheses, the number of open parentheses, and the current string being formed.

If the number of complete pairs is equal to n and the number of open parentheses is zero, we have a valid combination, and we can add it to our answer list.

If the number of complete pairs exceeds n or the number of open parentheses exceeds the number of complete pairs, we can return early as this is not a valid combination.

If the number of open parentheses is less than n, we can add an opening parenthesis and make a recursive call. If the number of open parentheses is greater than zero, we can add a closing parenthesis and make another recursive call.

And we’re done!

Solution in Python



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

        def dfs(completePairs, open, currentStr):
            if completePairs == n and open == 0:
                ans.append(currentStr)
                return
            
            if completePairs > n or open > n - completePairs:
                return

            if open < n:
                dfs(completePairs, open + 1, currentStr + "(")
            if open > 0:
                dfs(completePairs + 1, open - 1, currentStr + ")")
            return

        dfs(0, 0, "")
        return ans

Complexity

  • Time: $O(2^{2n})$
    Since there are $2 \times n$ positions to fill, and each position can be either an opening or closing bracket, the time complexity is $O(2^{2n})$.

  • Space: $O(2^{2n})$
    Since we are storing all the valid combinations of parentheses in the answer list, the space complexity is also $O(2^{2n})$.

And we are done.