Medium Constrained Generation Backtracking
In plain English: Generate every possible way to arrange n pairs of parentheses so they're all properly matched.
Backtrack with two counters: open and close. You can add '(' if open < n, and ')' if close < open. The close < open constraint ensures validity. Base case: length == 2*n.
Prompt
Given n pairs of parentheses, generate all combinations of well-formed (valid) parentheses.
Try to write it from scratch before scrolling down.
Solution
def generate_parenthesis(n):
result = []
def backtrack(path, open_count, close_count):
if len(path) == 2 * n:
result.append(''.join(path))
return
# can add '(' as long as we haven't used all n opens
if open_count < n:
path.append('(')
backtrack(path, open_count + 1, close_count)
path.pop()
# can add ')' only when unmatched opens exist, ensuring validity
if close_count < open_count:
path.append(')')
backtrack(path, open_count, close_count + 1)
path.pop()
backtrack([], 0, 0)
return result
# Test: generate_parenthesis(3)
# == ["((()))","(()())","(())()","()(())","()()()"]
# Test: generate_parenthesis(1) == ["()"]