Sponsored
Sponsored
The key idea here is to build the solution by choosing either an opening or a closing parenthesis at each step. We make sure that any partial solution is valid - at any point in time, the number of closing parentheses cannot exceed the number of opening ones. We also stop adding parentheses when we have used 'n' of each.
Time Complexity: O(4^n/sqrt(n)) due to the Catalan number growth.
Space Complexity: O(n) for recursion stack.
1def generateParenthesis(n):
2 def backtrack(S = '', left = 0, right = 0):
3 if len(S) == 2 * n:
4 result.append(S)
5 return
6 if left < n:
7 backtrack(S + '(', left + 1, right)
8 if right < left:
9 backtrack(S + ')', left, right + 1)
10
11 result = []
12 backtrack()
13 return result
14
15# Example Usage
16print(generateParenthesis(3))In Python, the function uses a helper function 'backtrack' that takes the current string and counts of left and right parentheses. The recursive logic ensures that any partially constructed string is valid by allowing adding a '(' if the left count hasn't reached 'n', and a ')' if '(' count is greater than ')'. The function is simple yet effectively searches through the possibilities.