Loading...
Loading...
Loading...
Rahul is building a small calculator app for his mini project. To test it, he needs every correct way to write n pairs of round brackets. A bracket string is correct when every ( is closed by a ) after it, and no ) comes before its (. For example, (()) and ()() are correct, but )( and (() are not.
His app can only handle brackets nested at most k deep. In (()) the inner pair sits inside the outer one, so it is nested 2 deep, while ()() is nested only 1 deep.
Print every correct string with exactly n pairs that is nested at most k deep, one per line, in dictionary order where ( comes before ).
Example 1
Input
3 2
Output
(()()) (())() ()(()) ()()()
((())) is nested 3 deep, so 4 of the 5 correct strings are printed.
Example 2
Input
2 1
Output
()()
Only ()() stays 1 deep.
Try the problem first. Open one hint at a time.
Build the string one bracket at a time. Track how many ( and how many ) you have used.
You may add ( while you have used fewer than n of them and the open depth (opened minus closed) is below k.
You may add ) only while you have closed fewer brackets than you opened. That rule alone keeps every string correct.
Try ( before ) at each step and the strings come out in dictionary order. Remove the bracket after each recursive call.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor