Generate Parentheses

Problem Description

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

Examples

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def generateParenthesis(n: int) -> List[str]:
    def backtrack(open_count: int, close_count: int, path: str, result: List[str]) -> None:
        if len(path) == 2 * n:
            result.append(path)
            return
        
        if open_count < n:
            backtrack(open_count + 1, close_count, path + "(", result)
        if close_count < open_count:
            backtrack(open_count, close_count + 1, path + ")", result)
    
    result = []
    backtrack(0, 0, "", result)
    return result

Java Solution


class Solution {
    public List generateParenthesis(int n) {
        List result = new ArrayList<>();
        backtrack(0, 0, n, "", result);
        return result;
    }
    
    private void backtrack(int openCount, int closeCount, int n, String path, List result) {
        if (path.length() == 2 * n) {
            result.add(path);
            return;
        }
        
        if (openCount < n) {
            backtrack(openCount + 1, closeCount, n, path + "(", result);
        }
        if (closeCount < openCount) {
            backtrack(openCount, closeCount + 1, n, path + ")", result);
        }
    }
}

C++ Solution


class Solution {
private:
    void backtrack(int openCount, int closeCount, int n, string& path, vector& result) {
        if (path.length() == 2 * n) {
            result.push_back(path);
            return;
        }
        
        if (openCount < n) {
            path.push_back('(');
            backtrack(openCount + 1, closeCount, n, path, result);
            path.pop_back();
        }
        if (closeCount < openCount) {
            path.push_back(')');
            backtrack(openCount, closeCount + 1, n, path, result);
            path.pop_back();
        }
    }
    
public:
    vector generateParenthesis(int n) {
        vector result;
        string path;
        backtrack(0, 0, n, path, result);
        return result;
    }
};

JavaScript Solution


/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const result = [];
    
    function backtrack(openCount, closeCount, path) {
        if (path.length === 2 * n) {
            result.push(path);
            return;
        }
        
        if (openCount < n) {
            backtrack(openCount + 1, closeCount, path + "(");
        }
        if (closeCount < openCount) {
            backtrack(openCount, closeCount + 1, path + ")");
        }
    }
    
    backtrack(0, 0, "");
    return result;
};

C# Solution


public class Solution {
    public IList GenerateParenthesis(int n) {
        var result = new List();
        Backtrack(0, 0, n, "", result);
        return result;
    }
    
    private void Backtrack(int openCount, int closeCount, int n, string path, List result) {
        if (path.Length == 2 * n) {
            result.Add(path);
            return;
        }
        
        if (openCount < n) {
            Backtrack(openCount + 1, closeCount, n, path + "(", result);
        }
        if (closeCount < openCount) {
            Backtrack(openCount, closeCount + 1, n, path + ")", result);
        }
    }
}

Complexity Analysis

Time Complexity: O(4ⁿ/√n) - nth Catalan number
Space Complexity: O(n) for the recursion stack

Solution Explanation

This solution uses backtracking to generate all valid combinations. Here's how it works:

Keep track of the count of open and closed parentheses
Add an open parenthesis if we haven't used all n pairs
Add a closing parenthesis if we have more open than closed
When the current combination reaches length 2*n, add it to result

Key points:

We can add an open parenthesis if openCount < n
We can add a closing parenthesis if closeCount < openCount
The solution generates only valid combinations
Each combination has exactly n pairs of parentheses