Generate Parantheses

For a given n , generate all strings of size 2*n with well formed parantheses.

Example Test Cases

Sample Test Case 1

N: 2
Expected Output:

• ()()
• (())

Sample Test Case 2

N: 3
Expected Output:

• ((()))
• (()())
• ()(())
• (())()
• ()()()

Solution

We can solve this problem by generating all the possible strings of length 2^n , such that each character in the string is either ( or ) , and then printing only those strings which are balanced. There will be a total of 2²ⁿ such strings.

Implementation

We can implement the above algorithm using backtracking as shown below:

Implementation

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

// Function to check if the string is valid paranthesis or not.
bool isValid(string str) {
    int cnt = 0;
    for(int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            cnt++;
        }
        else if (str[i] == ')') {
            cnt--;
        }
        if (cnt < 0) {
            return false;
        }
    }
    if (cnt == 0) {
        return true;
    }
    return false;
}

// Recursive function to backtrack and generate all the possible combinations    
void backtrack(string& str, int i, int n) {
    // Once the full string is generate, print the string if it is valid.
    if (i == n) {
        if (isValid(str)) {
            cout << str << "\n";
        }
    }
    else {
        str.push_back('(');
        backtrack(str, i + 1, n);
        str.pop_back();

        str.push_back(')');
        backtrack(str, i + 1, n);
        str.pop_back();
    }
}

void generateParenthesis(int n) {
    string str;
    backtrack(str, 0, n);
}

int main() {
    int n = 3;
    generateParenthesis(2*n);
    return 0;
}