Crack the Backend

Problem Statement

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Well-formed means every opening ( has a matching closing ) and they are properly nested (e.g. ()(), (()) for n=2).

We have n open and n close parentheses. We build a string from left to right. At any step we can add ( only if we have used fewer than n opens, and we can add ) only if the number of closes so far is less than the number of opens (so we never have an unmatched )).

Key Observations

Backtracking with (open, close): open = number of ( used, close = number of ) used. When open == n && close == n, we have a valid string — add it. Otherwise: if open < n, add ( and recurse; if close < open, add ) and recurse. After each recursive call we backtrack (remove the added char). This ensures we only generate valid sequences.

Approach

High-level: DFS(open, close, path). If open == n && close == n, add path. If open < n, add '(', recurse, remove. If close < open, add ')', recurse, remove.

Steps: dfs(open, close, path): if open == n && close == n add path and return. if open < n: path += '(', dfs(open+1, close), path pop. if close < open: path += ')', dfs(open, close+1), pop.

Implementation

Java

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    dfs(n, 0, 0, new StringBuilder(), result);
    return result;
}

void dfs(int n, int open, int close, StringBuilder path, List<String> result) {

    if (open == n && close == n) { result.add(path.toString()); return; }
    if (open < n) { path.append('('); dfs(n, open+1, close, path, result); path.setLength(path.length()-1); }
    if (close < open) { path.append(')'); dfs(n, open, close+1, path, result); path.setLength(path.length()-1); }
}

Test Cases

Example 1

Input

n = 3

Expected

["((()))","(()())","(())()","()(())","()()()"]

Explanation

All 5 valid combinations.

Complexity Analysis

Time: O(4^n / sqrt(n)).
Space: O(n).

Follow-ups

Valid Parentheses: check if a string is well-formed.