Given a number of parenthesis pairs n, produce every distinct string made up of exactly n ( characters and n ) characters that is well-formed.
A string counts as well-formed when each ( can be paired with a later ), with pairs properly nested. Equivalently, as you read the string from left to right, the running count of ) characters must never rise above the running count of (, and at the very end the two counts must be equal.
Implement the function generateParenthesis(n), which returns the list of all such well-formed strings. The order in which you return them is not significant.
Example 1:
Input: n = 2
Output: ["(())","()()"]
Explanation: with two pairs there are exactly two well-formed strings, and both appear above.
Example 2:
Input: n = 4
Output: ["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]
Constraints:
n opening and n closing parentheses.This exercise evaluates a candidate's grasp of constraint-based enumeration and combinatorial generation, together with incremental string construction — skills commonly assessed in software engineering and data engineering interviews. Be prepared to discuss how the number of valid outputs grows with n.