namespace LeetCode.Logic;

public class ParenthesesGenerator
{
    /// <summary>
    /// Generates all combinations of well-formed parentheses for n pairs.
    /// Time Complexity: O(4^n / sqrt(n)) - This is related to the nth Catalan number.
    /// Space Complexity: O(n) - Maximum depth of the recursion stack.
    /// </summary>
    public IList<string> GenerateParenthesis(int n)
    {
        var result = new List<string>();
        Backtrack(result, string.Empty, 0, 0, n);
        return result;
    }

    private void Backtrack(List<string> result, string current, int open, int close, int max)
    {
        // Base case: if the current string length is max * 2, we found a valid combination
        if (current.Length == max * 2)
        {
            result.Add(current);
            return;
        }

        // We can add an opening bracket if we still have some left
        if (open < max)
        {
            Backtrack(result, current + "(", open + 1, close, max);
        }

        // We can add a closing bracket if it doesn't exceed the number of opening brackets
        if (close < open)
        {
            Backtrack(result, current + ")", open, close + 1, max);
        }
    }
}