Why it works
- A ")" is added only while close < open, so at every point of the string no more ")" than "(" stand before it: no string can go wrong on the way.
- A "(" is added only while open < n, so a string never has more than n of them; when it reaches 2n brackets, open = close = n and it is balanced.
- Every balanced string is reached: at each place it puts either a "(" or a ")" that the counts allow, and the run tries both. Branches the counts forbid are never entered, so nothing has to be checked at the end.
Complexity
Time O(√n × 4ⁿ): the counts let through O(4ⁿ / √n) beginnings of strings in all (they grow like the Catalan numbers), and each call builds its own string in up to 2n steps. Memory O(n²) besides the answer: the call stack is 2n deep, and each call keeps its own string of up to 2n brackets.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗