Generate Parentheses (Well-formed Combinations)?

Follow on:

List<string> GenerateParenthesis(int n)

List<string> result = new List<string>();

Generate("", 0, 0, n, result);

return result;

void Generate(string current, int open, int close, int max,

List<string> result)

if (current.Length == max * 2)

result.Add(current);

return;

if (open < max)

Generate(current + "(", open + 1, close, max, result);

if (close < open)

Generate(current + ")", open, close + 1, max, result);

Explanation:

Use backtracking to add '(' and ')' only when valid.