// Header files
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

// This function checks for well formedness of the passed string.
bool valid(string s)
{
    stack<char> st;
    for(int i=0;i<s.length();i  )
    {
        char x=s[i];
        if(x=='(')
        {
            st.push(x);
            continue;
        }
        
        if(st.empty())
        return false;
        
        st.pop();
    }
    
    return st.empty();
}

// This function generates all  combination of parenthesis and only checks well formedness of string whose length is equal to n.
void generate(int n,string s)
{
    if(s.length()==n)
    {
        bool balanced = valid(s);
        if(balanced)
        cout<<s<<endl;
        return;
    }
    
    generate(n,s "(");
    generate(n,s ")");
}

// Driver code
int main()
{
    int n;
    cin>>n;
    generate(n,"");

    return 0;
}

What i am trying to achieve is to generate all possible parenthesis of upto length n. And check well formedness/ balance of the so formed strings whose size is N. My program terminates without printing anything. Please help!

Eg for n=3, Input: N = 3 Output: ((()))

(()())

(())()

()(())

()()()

Order does not matter.

My output doesn't show anything.

Refer : https://practice.geeksforgeeks.org/problems/generate-all-possible-parentheses/1

CodePudding user response：

//c   program to print all the combinations of 
balanced parenthesis.
#include <bits/stdc  .h>
using namespace std;
//function which generates all possible n pairs 
of balanced parentheses.
//open : count of the number of open parentheses 
used in generating the current string s.
//close : count of the number of closed 
parentheses used in generating the current string 
s.
//s : currently generated string/
//ans : a vector of strings to store all the 
valid parentheses.
void generateParenthesis(int n, int open, int 
close, string s, vector<string> &ans){
  //if the count of both open and close 
parentheses reaches n, it means we have generated 
a valid parentheses.
  //So, we add the currently generated string s 
to the final ans and return.
if(open==n && close==n){
    ans.push_back(s);
    return;
}  
  //At any index i in the generation of the 
string s, we can put an open parentheses only if 
its count until that time is less than n.
if(open<n){
    generateParenthesis(n, open 1, close, s "{", 
ans);
}
//At any index i in the generation of the string             
s, we can put a closed parentheses only if its 
count until that time is less than the count of 
open parentheses.
if(close<open){
    generateParenthesis(n, open, close 1, s "}", 
ans);
}
  
}
int main() {
int n = 3;
  //vector ans is created to store all the 
possible valid combinations of the parentheses.
vector<string> ans;
  //initially we are passing the counts of open 
and close as 0, and the string s as an empty 
string. 
generateParenthesis(n,0,0,"",ans);
  //Now, here we print out all the combinations.
for(auto s:ans){
    cout<<s<<endl;
}
return 0;
}