22. Generate Parentheses — LeetCode(Python)
I got you!
Problem:
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
Solution:
def backtrack(open_n, closed_n, path): if open_n == closed_n == n:
res.append(path)
return
if open_n < n:
backtrack(open_n + 1, closed_n, path + "(")
if closed_n < open_n:
backtrack(open_n, closed_n + 1, path + ")")
res = []
backtrack(0, 0, "")
return res
Explanation —
We use a backtracking algorithm here.
We use depth-first search (DFS) to find out all valid combinations of parentheses.
If there are any open parentheses available, we add one to the path and recurse on our function.
If the number of closing parentheses used is less than the number of open parentheses we have used, we add a closing parentheses and recurse on our function.
A path is only valid if the number of open and closed parentheses is equal. And if that is the case, we add the created string to our results.
Finally, we return the list of valid strings.
Time and Space Complexity —
In a backtracking algorithm, generally, the time complexity is O(b^d), where b is the branching factor and d is the maximum depth of the recursion tree.
In this case, our branching factor is 2 since we make two recursive calls per function and create a binary tree.
The maximum depth of our recursion tree is 2n since it is the length of the string we are required to find.
Our space complexity and time complexity is going to be the same since we are using recursion here, and the recursion stack could be holding all nodes in the tree at some point in time.
Therefore, if n is the number of pairs of parentheses we are given,
Time Complexity: O(2^(2n)) ~ O(4^n)
Space Complexity: O(2^(2n)) ~ O(4^n)
A more rigorous exploration would require us to understand a very high level of mathematical analysis and Catalan numbers, which would give the time and space complexities to be O((4^n)/sqrt(n)).
Though our answer is not as accurate, it does give a good upper bound on the algorithm, which should not be a problem in an interview setting, if that is what is worrying you.
