Write generate_parens(n: int) -> list[str] that returns every string made of n opening and n closing parentheses that is balanced (reading left to right, the number of ) never exceeds the number of ( so far, and the totals match). Return them sorted (plain string order, where "(" < ")").
generate_parens(0) # [""]
generate_parens(1) # ["()"]
generate_parens(2) # ["(())", "()()"]
generate_parens(3) # ["((()))", "(()())", "(())()", "()(())", "()()()"]
Constraints: 0 <= n <= 12. The number of answers is the Catalan number C(n), which is 208,012 at n = 12.
Generating all 2^(2n) strings and filtering is far too slow at n = 12; aim for work proportional to the size of the output.
Show hint
Build the strings one character at a time and never extend a prefix that can no longer become balanced. Which of ( and ) is allowed next depends only on how many of each you have used so far.