22. Generate Parentheses
Problem
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Example 2:
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.