MediumBacktracking
Generate Parentheses
Generate valid parentheses combinations
Solution Approach
Backtracking with constraints: open < n and close < open. Build valid combinations.
Implementation
def generateParentheses(n):
result = []
def backtrack(open_count, close_count, current):
if len(current) == 2 * n:
result.append(current)
return
if open_count < n:
backtrack(open_count + 1, close_count, current + "(")
if close_count < open_count:
backtrack(open_count, close_count + 1, current + ")")
backtrack(0, 0, "")
return resultComplexity Analysis
Time Complexity
O(4^n/√n)Space Complexity
O(n)Complexity
Time:O(4^n/√n)
Space:O(n)
Asked at
GoogleAmazonFacebook