Logo for ammarahmed.ca
Medium
Jun 09, 2025
#stack
#recursion

22. Generate Parentheses

Problem

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

Example 1:

1Input: n = 3 2Output: ["((()))","(()())","(())()","()(())","()()()"] 3

Example 2:

1Input: n = 1 2Output: ["()"] 3

Constraints:

  • 1 <= n <= 8

    Approach

    We can solve this problem recursively by using the idea of open and closed parentheses. We can see that the number of open and closed parentheses in a well-formed parentheses string must be equal to n. As in, open = closed = n. However, when generating the string, the number of closed parentheses must not exceed the number of open parentheses. For example, if we have "(())", the number of open and closed parentheses is equal to 2. Therefore, we cannot add a closed parentheses here because closed must always be less than or equal to open.

    Using this principle, we have the following rules for our recursive function:

    • Base case: If open == closed == n, we are finished with the formation and can add the parentheses string to our result
      • open < n: If open < n, then we can add more open parentheses
        • closed < open: If closed < open, we can add more closing parentheses

          Using these rules alongside a stack that is passed with each recursive function, we can form our parentheses.

          Complexity

          Time: O(4^n)

          Since we have 2 possibilites at each step and there are 2n steps, we have 2 ^ 2n = 4^n

          Space: O(n)

          Since it's recursive, we'll be creating 2n calls on the stack at a time.

          Solution

          1import "strings" 2func backtrack(stack []string, n, open, closed int, result *[]string) { 3 if open == closed && closed == n { 4 *result = append(*result, strings.Join(stack, "")) 5 return 6 } 7 8 if open < n { 9 stack = append(stack, "(") 10 backtrack(stack, n, open+1, closed, result) 11 stack = stack[:len(stack)-1] 12 } 13 14 if closed < open { 15 stack = append(stack, ")") 16 backtrack(stack, n, open, closed+1, result) 17 stack = stack[:len(stack)-1] 18 } 19} 20func generateParenthesis(n int) []string { 21 var ( 22 stack []string 23 result []string 24 ) 25 backtrack(stack, n, 0, 0, &result) 26 return result 27} 28