Java : Generate Parentheses

PROBLEM STATEMENT

Given an integer n, representing the number of pairs of parentheses, generate all combinations of well-formed (structurally valid) parentheses.

For example, if n=3, the expected output is: ["((()))", "(()())", "(())()", "()(())", "()()()"]

CLARIFYING QUESTIONS

• What defines a "well-formed" string? (A string where each open parenthesis has a corresponding, correctly nested close parenthesis.)

• What are the constraints on n? (Typically n is small, e.g., 1≤n≤8, which makes a recursive solution feasible.)

INTUITION

The core idea is to build the parenthesis strings character by character using backtracking. At each step, there is a choice: add an open parenthesis ( or a close parenthesis ).

A valid solution is built by enforcing two critical constraints at every step:

1. An open parenthesis ( can be added only if the count of open parentheses used so far is less than n.
2. A close parenthesis ) can be added only if the count of close parentheses is strictly less than the count of open parentheses. This ensures the string prefix remains valid at all times.

THE APPROACH

This problem is solved using a recursive Depth-First Search (DFS) algorithm, also known as backtracking. A helper function is used to build the string incrementally while tracking the state.

The state consists of:

1. The count of open parentheses used (openP).
2. The count of closed parentheses used (closeP).
3. The current string being built (s).

The reason for this approach: Backtracking is ideal for "generate all combinations" problems. It explores all potential paths (adding ( or )) and "prunes" (stops exploring) any path that violates the well-formed constraints. This avoids generating invalid combinations from the start.

ALGORITHM BREAKDOWN

Step 1: Initialize an empty list res to store the final valid strings.

Step 2: Define a recursive function dfs(openP, closeP, s, n, res).

Step 3: Base Case (Success): Inside dfs, check if the string is complete. The condition openP == closeP && openP + closeP == n * 2 (which simplifies to openP == n && closeP == n) means n pairs have been used and the string is balanced. Add the current string s to res and return.

Step 4: Recursive Choice 1 (Add Open): Check if an open parenthesis ( can be added. If openP < n, make a recursive call with updated state: dfs(openP + 1, closeP, s + "(", ...).

Step 5: Recursive Choice 2 (Add Close): Check if a close parenthesis ) can be added. If closeP < openP, make a recursive call with updated state: dfs(openP, closeP + 1, s + ")", ...).

The recursion unwinds after all valid paths from a given state have been explored.

SOLUTION

class Solution {
    public List<String> generateParenthesis(int n) {
        // 1. Initialize the result list
        List<String> res = new ArrayList<>();
 
        // 2. Start the backtracking process
        // Initial state: 0 open, 0 close, empty string
        dfs(0, 0, "", n, res);
 
        return res;        
    }
 
    private void dfs(int openP, int closeP, String s, int n, List<String> res) {
        
        // 3. Base Case: The string is complete and balanced.
        if (openP == closeP && openP + closeP == n * 2) {
            res.add(s);
            return;
        }
 
        // 4. Recursive Choice 1: Add an open parenthesis
        // Constraint: Can only add if we haven't reached the max (n)
        if (openP < n) {
            dfs(openP + 1, closeP, s + "(", n, res);
        }
 
        // 5. Recursive Choice 2: Add a close parenthesis
        // Constraint: Can only add if # of close < # of open
        if (closeP < openP) {
            dfs(openP, closeP + 1, s + ")", n, res);
        }
    }    
}        

KEY IMPLEMENTATION POINTS

• The state is tracked efficiently using two integer counters, openP and closeP.

• Constraint 1 (Adding '('): The if (openP < n) check ensures no more than n open parentheses are ever added to any single path.

• Constraint 2 (Adding ')'): The if (closeP < openP) check is the most critical rule. It mathematically guarantees that a closing parenthesis is only added if there is a corresponding, unmatched open parenthesis available. This prevents invalid strings like ()) from ever being built.

TIME AND SPACE COMPLEXITY

Time Complexity: O(n4n)

• This is not O(2n). The number of valid combinations is given by the n-th Catalan number (Cn).

• The recursion tree is heavily pruned by the constraints.

• For each of the Cn valid sequences, O(n) work is done to build the string (in Java, string concatenation can be O(n), though StringBuilder would optimize this).

• The n-th Catalan number is approximately nnπ4n, so the time complexity is bounded by O(n⋅Cn) or O(n4n).

Space Complexity: O(n)

• The space complexity is determined by the maximum depth of the recursion stack.

• In the worst case, the stack will go 2n levels deep (e.g., to build ((...))).

• Therefore, the auxiliary space required is O(n). (This does not count the output list, which stores the Cn results).

EFFICIENCY NOTES

This backtracking solution is optimal because it explores only valid paths. It does not generate invalid candidates and then check them; it prunes invalid branches immediately, leading to the Catalan number-based time complexity.

💡 KEY TAKEAWAY

Backtracking is a powerful technique for generation problems (permutations, combinations, subsets). The solution's effectiveness comes from defining simple, strict constraints (like openP < n and closeP < openP) that prune the search space and guarantee only valid solutions are constructed.

#DSA #Algorithms #Backtracking #Recursion #TechInterview #Java