Discussion on: Daily Challenge #101 - Parentheses Generator

[samvidmistry]

I tried using C++. Haven't tested it much. I know there exists a method in C++ to generate all permutations of a string. But this program is better optimized. It doesn't check all permutations. It stops following a sequence whenever it runs into a condition from where a valid sequence cannot be generated. For example, whenever number of closing braces are more than number of opening braces, there is no point following that recursion because it will never generate any valid permutations.

/**
 * Parentheses Generator 
 * https://dev.to/thepracticaldev/daily-challenge-101-parentheses-generator-5d12
 */
#include <iostream>
#include <stack>

using namespace std;

bool check_balanced_parans(string s) {
    stack<char> stack;
    for(auto it = s.begin(); it != s.end(); it++) {
        if(*it == '(') {
            stack.push(*it);
        } else {
            if (stack.empty() || stack.top() == ')') {
                return false;
            } else {
                stack.pop();
            }
        }
    }

    return stack.empty();
}

void generate_all_permutations(int n, int i, string s, int open, int close) {
    if(close > open) return;
    if(open > n / 2 + 1) return;

    if(i == 0) {
        if(check_balanced_parans(s)) cout << s << endl;
    } else {
        s.push_back('(');
        generate_all_permutations(n, i - 1, s, open + 1, close);
        s.pop_back();
        s.push_back(')');
        generate_all_permutations(n, i - 1, s, open, close + 1);
    }
}

int main() {
    int n;
    cin >> n;

    string s;
    generate_all_permutations(n * 2, n * 2, s, 0, 0);

    return 0;
}