Print all combinations of balanced parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example:

• Input: n = 2
• Output: ["(())", "()()"]

Approach: Backtracking

To solve this problem, we use backtracking to explore all possible combinations of parentheses. The idea is to generate strings by adding '(' and ')' recursively, while ensuring that at any point:

• We do not have more closing parentheses ')' than opening '('.
• We do not exceed n pairs of parentheses.

Generate Parentheses Code in JavaScript:

function generateParentheses(n) {
    const result = [];

    function backtrack(openCount, closeCount, current) {
        if (current.length === n * 2) {
            result.push(current);
            return;
        }

        if (openCount < n) {
            backtrack(openCount + 1, closeCount, current + '(');
        }

        if (closeCount < openCount) {
            backtrack(openCount, closeCount + 1, current + ')');
        }
    }

    backtrack(0, 0, '');
    return result;
}

// Example Usage
console.log(generateParentheses(2)); // Output: ["(())", "()()"]

Explanation of the Code

1. Backtracking Function: The backtrack function is called recursively to build the combinations.
2. Parameters:
   • openCount: Number of '(' used so far.
   • closeCount: Number of ')' used so far.
   • current: Current string being built.
3. Base Case: If the length of current equals n * 2 (since each pair has two characters), we have a valid combination.
4. Recursive Calls:
   • Add '(' if possible: If openCount is less than n, we can add another '('.
   • Add ')' if valid: If closeCount is less than openCount, we can add a ')' to maintain balance.

Recursive State Tree (n = 2)

The diagram below represents the recursive state tree for generating parentheses with n = 2.

Explanation of the Diagram:

• Root Node A (“Start: ‘’”): Start with an empty string, with open and close counts at 0.
• Node B1 (“Add ‘(’: ‘(’ (open=1, close=0)”): Add an opening parenthesis '(' to the string, incrementing open to 1.
• Node C1 (“Add ‘(’: ‘((’ (open=2, close=0)”): Add another '(', incrementing open to 2.
• Node D1 (“Add ‘)’: ‘(()’ (open=2, close=1)”): Now we must add a closing parenthesis ')' since open has reached n.
• Node E1 (“Add ‘)’: ‘(())’ (open=2, close=2)”): Add another ')', reaching n pairs, and we have a valid combination '(())'.
• Node C2 (“Add ‘)’: ‘()’ (open=1, close=1)”): Backtrack to a valid state and add ')'.
• Node D2 (“Add ‘(’: ‘()(’ (open=2, close=1)”): Add another '(', creating open=2.
• Node E2 (“Add ‘)’: ‘()()’ (open=2, close=2)”): Add the last ')' to form another valid combination "()()".

Key Points to Remember:

1. Recursive Exploration: Explore all possible valid combinations by adding '(' and ')'.
2. Backtracking: Use backtracking to undo the last action and explore other possibilities when necessary.
3. Valid Parentheses Check: Maintain the condition that at no point can the count of ')' exceed the count of '('.

.