Generate Parentheses

Generate Parentheses is a classic backtracking problem where the goal is to generate all possible combinations of well-formed parentheses for a given number n. The algorithm builds the string step by step and ensures validity by never allowing the number of closing parentheses to exceed the number of opening ones. This constraint prunes invalid branches early and makes the search efficient.

function generateParentheses(n):
    result = []
    backtrack('', 0, 0)

    function backtrack(current, open, close):
        if length(current) == 2 * n:
            add current to result
            return

        if open < n:
            backtrack(current + '(', open + 1, close)

        if close < open:
            backtrack(current + ')', open, close + 1)

    return result