Generate Parentheses Problem and Solution

1. Introduction

A comprehensive guide to solving the "Generate Parentheses" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "Generate Parentheses" problem requires generating all combinations of well-formed parentheses for a given number n.

2. Problem

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

3. Solution in C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void backtrack(vector<string> &result, string &current, int open, int close, int max) {
    if (current.length() == max * 2) {
        result.push_back(current);
        return;
    }
    if (open < max) {
        current += '(';
        backtrack(result, current, open + 1, close, max);
        current.pop_back();
    }
    if (close < open) {
        current += ')';
        backtrack(result, current, open, close + 1, max);
        current.pop_back();
    }
}

vector<string> generateParenthesis(int n) {
    vector<string> result;
    string current;
    backtrack(result, current, 0, 0, n);
    return result;
}

// Example usage
int main() {
    vector<string> combinations = generateParenthesis(3);
    for (const string &s : combinations) {
        cout << s << endl;
    }
    return 0;
}

Output:

((()))
(()())
(())()
()(())
()()()

Explanation:

1. generateParenthesis in C++ uses backtracking.

2. It builds strings by adding '(' or ')' characters, ensuring valid parentheses.

3. The recursion stops when the string reaches twice the length of n.

4. Returns all possible well-formed parentheses combinations.

4. Solution in Java

import java.util.*;

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

    private static void backtrack(List<String> result, String cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            result.add(cur);
            return;
        }
        if (open < max)
            backtrack(result, cur + "(", open + 1, close, max);
        if (close < open)
            backtrack(result, cur + ")", open, close + 1, max);
    }

    // Example usage
    public static void main(String[] args) {
        List<String> combinations = generateParenthesis(3);
        for (String s : combinations) {
            System.out.println(s);
        }
    }
}

Output:

((()))
(()())
(())()
()(())
()()()

Explanation:

1. Java's generateParenthesis method also uses backtracking.

2. It constructs the string by adding '(' and ')' while maintaining valid parentheses.

3. Stops when the string length equals twice the given n.

4. Outputs all combinations of well-formed parentheses.

5. Solution in Python

def generate_parenthesis(n):
    def backtrack(s='', left=0, right=0):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)

    result = []
    backtrack()
    return result

# Example usage
combinations = generate_parenthesis(3)
for combo in combinations:
    print(combo)

Output:

((()))
(()())
(())()
()(())
()()()

Explanation:

1. Python's generate_parenthesis uses a backtracking approach.

2. It constructs strings by adding '(' and ')' while ensuring the number of '(' is always greater or equal to ')'.

3. Stops the recursion when the string length is twice n.

4. Returns all valid combinations of parentheses.