Generate Parentheses - CPP Solution

1. Introduction

In this blog post, we explore a fascinating problem often encountered in coding interviews and algorithm challenges: generating all combinations of well-formed parentheses. The problem is a great way to understand recursion and backtracking in C++.

Problem

Given 'n' pairs of parentheses, the task is to write a function that generates all combinations of well-formed parentheses. A combination is considered well-formed if each opening parenthesis '(' has a corresponding closing parenthesis ')'.

2. Solution Steps

1. Use a recursive function to build the combinations.

2. Maintain two counters for the number of opening and closing parentheses used.

3. Add an opening parenthesis if there are any left to use.

4. Add a closing parenthesis if it would not lead to an imbalance.

5. When the total length of the combination equals 2 * n, add it to the result.

6. Use backtracking to explore all possible combinations.

3. Code Program

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

// Helper function for recursion
void backtrack(vector<string> &combinations, string &current, int open, int close, int max) {
    if (current.length() == max * 2) {
        combinations.push_back(current);
        return;
    }

    if (open < max) {
        current += '('; // Add an opening parenthesis
        backtrack(combinations, current, open + 1, close, max);
        current.pop_back(); // Remove the last parenthesis to backtrack
    }
    if (close < open) {
        current += ')'; // Add a closing parenthesis
        backtrack(combinations, current, open, close + 1, max);
        current.pop_back(); // Remove the last parenthesis to backtrack
    }
}

// Function to generate all combinations of well-formed parentheses
vector<string> generateParenthesis(int n) {
    vector<string> combinations;
    string current;
    backtrack(combinations, current, 0, 0, n);
    return combinations;
}

int main() {
    int n = 3;
    vector<string> result = generateParenthesis(n);
    cout << "All combinations of well-formed parentheses:" << endl;
    for (const string &comb : result) {
        cout << comb << endl;
    }
    return 0;
}

Output:

All combinations of well-formed parentheses:
((()))
(()())
(())()
()(())
()()()

Explanation:

1. The input '3' represents 3 pairs of parentheses.

2. The function recursively builds combinations, ensuring each addition maintains the balance of parentheses.

3. Opening parentheses are added as long as the count doesn't exceed 'n'.

4. Closing parentheses are added only if they do not outnumber the opening ones.

5. This process results in all valid combinations like "((()))", "(()())", and so on.

6. The use of backtracking allows the function to explore all possible well-formed combinations efficiently.