Enumerate Balanced Parenthesis Strings

### Problem Given the integer `pairs`, return every well-formed string that uses exactly that many opening parentheses and exactly that many closing parentheses. A string is well formed when parentheses can be matched in the usual nested way: the running number of closing parentheses never exceeds the running number of opening parentheses, and the totals agree at the end. Include each valid string once. The collection has no required ordering. ### Examples **Example 1** ```text Input: pairs = 2 Output: ["(())", "()()"] ``` These are the only two balanced strings using two pairs. **Example 2** ```text Input: pairs = 4 Output: ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"] ``` All fourteen strings are required. Listing the same strings in another order is equally acceptable. ### Constraints & Assumptions - The value of `pairs` is from 1 through 8, inclusive. - Each result contains only `(` and `)` and has length `2 * pairs`. - Return the complete collection, without duplicate strings; returning only its size is insufficient. - No particular generation algorithm or collection order is prescribed. ### Clarifying Questions to Ask - Must parentheses be nested as deeply as possible? No; adjacent balanced groups and nested groups are both valid. - Does matching totals alone establish validity? No; a prefix must never contain more closing than opening parentheses. ```hint Think about unfinished strings Once a prefix contains an unmatched closing parenthesis, appending more characters cannot repair that prefix. ``` ### What a Strong Answer Covers - Generation of every balanced string with exactly the requested pair count. - A rule that prevents invalid prefixes without excluding valid completions. - A proof that valid strings are neither missed nor emitted twice. - An output-sensitive complexity bound and separate accounting for recursion and returned strings. ### Follow-up Questions - If only the number of valid strings were requested, how could you count them without constructing every string?