Generate Parentheses

113.Generate Parentheses

Backtracking

String

Problem Statement:

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

Algorithm:

1. Use backtracking to build all possible combinations of parentheses by placing open ( and close ) parentheses at each step.
2. Track the number of open and close parentheses used so far:
   • If the number of close parentheses exceeds the number of open parentheses, return (invalid state).
   • If the number of open parentheses exceeds n, return (invalid state).
3. When the current string reaches a length of 2 × n and the number of open and close parentheses is equal, add it to the result.
4. Recursively try adding both open and close parentheses to the current string.

Complexity:

Time: O(4^n / √n), as this is related to the nth Catalan number | Space: O(n), for the recursion stack.

Java Implementation:

import java.util.*;

public class Solution {
    public List generateParenthesis(int n) {
        List res = new ArrayList<>();
        backtrack(new char[n * 2], 0, 0, res, 0, n);
        return res;  
    }

    void backtrack(char[] soFar, int open, int close, List res, int index, int n) {
        if (close > open || open > n) return;

        if (index == soFar.length) {
            if (open == close) res.add(String.valueOf(soFar));
            return;
        }

        // Add open parenthesis
        soFar[index] = '(';
        backtrack(soFar, open + 1, close, res, index + 1, n);

        // Add close parenthesis
        soFar[index] = ')';
        backtrack(soFar, open, close + 1, res, index + 1, n);      
    }
}
                

Python Implementation:

def generateParenthesis(n):
    res = []
    
    def backtrack(so_far, open_count, close_count):
        if len(so_far) == 2 * n:
            res.append(so_far)
            return
        
        if open_count < n:
            backtrack(so_far + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(so_far + ")", open_count, close_count + 1)
    
    backtrack("", 0, 0)
    return res
                

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    vector generateParenthesis(int n) {
        vector res;
        backtrack("", 0, 0, n, res);
        return res;
    }

    void backtrack(string soFar, int open, int close, int n, vector& res) {
        if (soFar.size() == 2 * n) {
            res.push_back(soFar);
            return;
        }

        if (open < n) {
            backtrack(soFar + "(", open + 1, close, n, res);
        }
        if (close < open) {
            backtrack(soFar + ")", open, close + 1, n, res);
        }
    }
};