22. Generate Parentheses

Generate Parentheses (Medium) Given n pairs of parentheses, return all possible well-formed combinations. The key idea is to build the string step by step while keeping it valid at every moment. We use backtracking to try adding "(" and ")", but we only add ")" when there are more open parentheses than closed ones so far. Backtracking Solution: Time Complexity: proportional to the number of valid combinations × n Space Complexity: O(n) extra space, not counting the output We track how many open and closed parentheses have been used. We can add "(" while openN ⟨ n, and we can add ")" while closedN ⟨ openN. When both counts reach n, we have one complete valid combination. The backtracking part is adding a parenthesis, exploring deeper, then popping it to try the next choice.