Generate Parentheses – 22. LeetCode

The “Generate Parentheses” problem is about creating all possible valid combinations of n pairs of parentheses. This problem is more about creativity and structure than raw computation—it involves figuring out how to place opening and closing parentheses such that the resulting sequence is valid.

In order for sequences to be valid they must be:

1. Balanced

• “()” is balanced.

• “(()())” is balanced.

• “((” is not balanced because it lacks closing parentheses.

• “())” is not balanced because there is an unmatched closing parenthesis.

2. Valid Order

• “(()())” is valid because at every position in the string, the number of opening parentheses is equal to or greater than the number of closing parentheses.

• “)(” is not valid because it starts with a closing parenthesis, which is unmatched.

• “(()))(())” is not valid because at one point, there are more closing parentheses than opening parentheses.

Brute Force Approach

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesesBruteForce {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    private boolean isValid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return balance == 0;
    }
}

• The brute force solution generates all possible combinations of 2n parentheses, then filters out the invalid ones. The generateAll function tries every possible sequence recursively, and isValid checks if the sequence is balanced.
• This approach works, but it is inefficient because it generates many invalid combinations, which are later discarded.

Optimal Approach: Backtracking with Recursion

The optimal solution uses backtracking. Backtracking is a recursive algorithmic strategy that explores all potential solutions by building them incrementally and abandoning (“backtracking”) paths that fail to satisfy the problem’s constraints.

This algorithm constructs valid combinations directly by maintaining two counters: one for the number of opening parentheses left to use and one for closing parentheses left to use. It ensures at each step that the combination remains valid by only adding:

1. An opening parenthesis if we still have some left.

2. A closing parenthesis if it doesn’t create an invalid state (e.g., more closing parentheses than opening).

This strategy avoids generating invalid combinations altogether, reducing unnecessary work and saving both time and space.

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private void backtrack(List<String> result, String current, int open, int close, int max) {
        // If the current combination is complete, add to result
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        // Add '(' if we can still add more
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        // Add ')' if it will not make the combination invalid
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}

Line By Line Explanation

1. Result Initialization

List<String> result = new ArrayList<>();

• This is the primary data structure for holding the results. Using a List allows dynamic resizing as combinations are generated.

2. Starting the Backtrack Process

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

• Separating the recursive logic into a helper method (backtrack) improves modularity and makes the code easier to understand.

3. Base Case

if (current.length() == max * 2) {
    result.add(current);
    return;
}

• A clear base case ensures the recursion does not continue indefinitely, improving readability and preventing stack overflow.

4. Adding an Open Parenthesis

if (open < max) {
    backtrack(result, current + "(", open + 1, close, max);
}

• Using a condition (open < max) avoids invalid combinations and unnecessary recursive calls, improving efficiency.

• Adding characters directly (current + “(“) ensures immutability, which is preferred in recursive solutions to avoid unintended side effects.

5. Adding a Close Parenthesis

if (close < open) {
    backtrack(result, current + ")", open, close + 1, max);
}

• Ensuring validity (close < open) prevents invalid combinations, reducing computational overhead.

• Recursive exploration follows a structured pattern, making the code more predictable and easier to debug.

6. Return

return result;

• A clean and predictable return value is essential for verifying correctness during automated testing.

Why This Code Works

This solution is clean, modular, and efficient, leveraging backtracking to generate combinations directly without creating invalid ones. Each step ensures adherence to problem constraints while maintaining simplicity and clarity, which are hallmarks of high-quality LeetCode solutions.