Generate Parentheses

Build every string of n pairs of parentheses that is balanced, without ever generating an invalid one.

The idea

Track how many open and close brackets have been placed so far instead of checking validity after the fact. An open bracket can always be added while open < n. A close bracket can only be added while close < open, which is exactly the rule that keeps the string balanced at every prefix.

Code

public static void Generate(int open, int close, int n, string path, List<string> result) {
    if (path.Length == 2 * n) { result.Add(path); return; }
    if (open < n) Generate(open + 1, close, n, path + "(", result);
    if (close < open) Generate(open, close + 1, n, path + ")", result);
}

Tips

• Both if statements can fire from the same call: try "(" first, and once that whole branch is done, come back and try ")" too.
• Because close < open is checked before recursing, every path built this way is guaranteed valid. There is nothing to reject afterwards.

In the .NET library

Building the string with path + "(" (instead of a mutable StringBuilder with an undo) works here because there is no explicit un-choose step: each recursive call gets its own copy of the string, so returning from it naturally discards that branch’s choice.