Print all possible combinations of balanced valid parenthesis

We have to write an algorithm to print all possible combinations of the balanced valid parenthesis for n pairs of parenthesis. A valid parenthesis is one that is properly opened and closed.

Example->  n = 3
For n=3, we have following 5 pairs of valid parenthesis.
   1. ((()))
   2. (())()
   3. ()(())
   4. (()())
   5. ()()() 

Note, any other combination is invalid.

Algorithm

Let’s start with an empty string and a variable size  =  2* n( n is the number of pairs). The variable size will determine the recursion depth.

Every time we will enter the recursion, we will keep on decreasing the current value of variable size by 1 and stop when the value of size becomes 0.

Add one to variable state(initially zero), if we appending the character “(” to the string and decrease variable state by one if we are appending the character ‘)’ to the string. The variable state tells that the parenthesis is balanced, i.e, the number of “(” characters in a string are equal to the character “)”.

If the value of variable state <0, it means somewhere in the string “)” appeared before “(“, which is invalid, hence stop.

Also, we keep on decreasing the value of variable n whenever we append the character “(” to the string. This is done to make sure, a string should only contain n “(” parenthesis only. (Neither greater nor lesser).

When the value of the variable size becomes 0, print a valid combination.

find_ways(state, n, size, pattern){
    if(state<0 || size<0 || n<0)
        return;
    
    if(size==0)
        print(pattern)
    
    find_ways(state+1, n-1, size-1, pattern+"(" );
    find_ways(state-1, n, size-1, pattern+")" );
    
    return 0; 
}

Implementation of the above algorithm in CPP

#include <bits/stdc++.h>
using namespace std;
int cnt=1;

int find_ways(int state, int n, int size, string str){

	if(state<0 || size<0 || n<0){
		return 0;
	}

	if(size == 0){
		cout<<cnt++<<". "<<str<<endl;
		return 0;
	}

	find_ways(state+1, n-1, size-1, str+'(');
	find_ways(state-1, n, size-1, str+')');

	return 0;
}

int main()
{
	int n;
	cin>>n;
	//vector<vector<int> > dp(3*n,vector<int> (3*n,0));
	find_ways(0,n, 2*n,"");

	return 0;
}

Output

1. ((()))
2. (()())
3. (())()
4. ()(())
5. ()()()

Please comment if you find anything incorrect about the above code/algorithm, or if there exists a better way to solve this problem. Click here to practice more problems.