You have n opening brackets ( and n closing brackets ). Return every string that uses all 2n of them and is balanced: reading left to right, you never meet a ) before there is an unmatched ( for it to close, and by the end every ( has been closed.
Each balanced string should appear exactly once. You may return them in any order.
Two pairs can either nest, one inside the other, or sit side by side. Strings such as "())(" use the right brackets but close one that was never opened.
Four pairs give 14 balanced strings, shown here in sorted order.
Constraints
1 <= n <= 8Build each string one character at a time and only take steps that can still lead to a balanced string, instead of generating everything and filtering.
Checking one string is easy. Walk it left to right with a counter depth: add 1 for (, subtract 1 for ). The string is balanced when depth never drops below 0 and ends at exactly 0.
Time O(n · Cₙ)Space O(n) besides the answer
The full walkthrough and code are part of Premium
2