Standard Bar Recursion · Subsequences Pattern O(4^n / sqrt(n)) valid sequences, each costing O(n) to build · O(n) recursion depth beyond the output
A market maker prints order tickets where every open bracket must be closed by a matching one, and the compliance desk wants the full catalogue of well-formed ticket templates exactly n brackets long. A template is built one character at a time: an open bracket may be printed while any remain unopened, and a close bracket may only follow if an open one is still pending. The builder branches on those two rules until every bracket pair is complete.
Input: An integer n, the number of bracket pairs.
Output: Every well-formed bracket string of length 2n, in the order the depth-first build produces them.
1 <= n <= 8Input: {"n":3}
Output: ["((()))","(()())","(())()","()(())","()()()"]
All five ways to interleave three open-close pairs without a close ever leading an open.
Input: {"n":1}
Output: ["()"]
One pair admits exactly one template.