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
The description was taken from https://leetcode.com/problems/generate-parentheses/.
#O(n*2^n) Time, O(n*2^n) Space
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
output = []
def backtrack(combo:list[str], left:int, right:int) -> None:
if len(combo) == 2 * n:
output.append("".join(combo))
return
if left < n:
combo.append("(")
backtrack(combo, left+1, right)
combo.pop()
if left > right:
combo.append(")")
backtrack(combo, left, right+1)
combo.pop()
backtrack([], 0, 0)
return outputIf we are given a problem that requires us to generate each possible combination of something, that is typically an indication that backtracking can be applied.
Backtracking is a Depth-First Search algorithm where we remove a choice whenever the DFS path yoyo returns to the given function. This allows us to circulate elements into each valid position so that we can generate each valid combination.
A general template for backtracking is to set a base case that appends a valid combination for a given DFS path to the output, check if a placement is valid, then make the placement. Once that placement is made, we'd go down a new DFS path with that placement and if that path didn't lead to a solution or it didn't lead to every solution like in this problem, we'd backtrack on the choice to make that placement by removing it from the combination.
This is what allows us to generate each combination, adding and removing a parenthesis for each position where it'd be valid.
Let's start by initializing our output array.
output = []
Next, we'll make our recursive backtrack function.
This function will take a current combination that will be correlated to a specific DFS path. It will also take counts for how many left and right parentheses reside in the current combination so that we will know what would constitute a valid placement later.
def backtrack(combo:list[str], left:int, right:int) -> None:
As mentioned previously, the first step in the template will be to see if the given function call yields a completed combination. In this case, we'll know if it has because the length of the combination will be equal to two times n, meaning we have n pairs.
If that is the case, we have reached the end of this DFS path so we will join the parentheses together to form a string, append that string to the output and return.
if len(combo) == 2 * n:
output.append("".join(combo))
return
The next step of the template is to make a valid placement if we can.
This probably should have been in the description, but the two rules that constitute a valid set of parentheses are:
The parentheses must be even.
There can’t be closing parentheses before opening ones.
These are the rules we will base our placement choices on.
If the count of left parentheses is less than n, then that means we still have left parentheses we need to place to get an even, n number of pairs due to the first rule.
If that is the case, we can place a left parenthesis into the combo and continue our DFS with this combination.
if left < n:
combo.append("(")
backtrack(combo, left+1, right)
Once the DFS yoyo has slung back up to us, we will backtrack on that choice by popping off the left parenthesis we chose to place.
combo.pop()
A left parenthesis is always going to be the starting character for each combination due to the second rule. However, this allows us to generate all valid parentheses for each other index besides index zero.
This is kind of like us saying, "Okay, we've seen a closing parenthesis for this second spot, now get out of here so we can give an opening parenthesis a chance to be in this second index.", and we do that for each index along the way for each combination in the recursive tree. We'd actually be doing that for the later indices before the earlier ones because this process would happen towards the bottom of the recursive tree before the top.
In this problem, we don't have one placement choice to make, but two, since we also need closing parentheses to place.
If the count of left parentheses is less than the count right ones, then placing a closing parenthesis would be a valid choice because we wouldn't be violating the second rule.
Same as the left parentheses, we will make a placement and backtrack on it so we can circulate other parentheses into the spot.
if left > right:
combo.append(")")
backtrack(combo, left, right+1)
combo.pop()
Now that we have our backtrack function built, we just need to make the initial call with an empty combo and the parenthesis counts of zero.
Once we have our output filled, we will return it.
backtrack([], 0, 0)
return output
The time and space complexity are extremely tricky for this one, but an intuitive estimation would be n*2^n. 2^n is the traditional space complexity for a backtracking algorithm since each index may require two choice child branches within a recursive tree and the join() function requires a time complexity of n.