BALANCED PARENTHESIS COUNT

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Recursion and Backtracking.

DIFFICULTY LEVEL:

Medium.

PROBLEM STATEMENT(SIMPLIFIED):

Rohan is now fond of balanced sequences, but suddenly he realized that he is in love with balanced parenthesis. Now he wants to know the number of the balanced parenthesis of length N. Help Rohan find the count.

For Example :

N = 4;
The balanced parenthesis sequence of length 4 are: (()), ()()

N=6;
The balanced parenthesis sequence of length 4 are: ((())), ()()(),()(()),(())(),(()()).

SOLVING APPROACH:

BRUTE FORCE:

Generate all (2 ^ (n)) possible parenthese strings and then validate each for being balanced.

If n = 4 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.

This lower bounds our time complexity.

Even if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(k, k/2) strings to consider for validation.

OPTIMIZATION:

You are encouraged to implement the above brute force on your own first ,before looking at the solution.
See original problem statement here

First, observe the recursion tree shown in the figure closely.Can you observe the key to this problem?
The Key is:

At each point of constructing the string of length k we make a choice.
We can place a "(" and recurse or we can place a ")" and recurse.
But we can’t just do that placement, we need 2 critical pieces of information.
The amount of left parens left to place.
The amount of right parens left to place.
We have 2 critical rules at each placement step.
We can place a left parentheses if we have more than 0 left to place.
We can only place a right parentheses if there are left parentheses that we can match against.
We know this is the case when we have less left parentheses to place than right parentheses to place.
Once we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.

ALGORITHM:

1.Recursion is the key here.

2.Divide the N into N/2 and N/2 (Count for open and closed parentheses ).

3.Select the open parentheses, add it to the result string and reduce its count and make a recursive call.

4.Select the close parentheses, add it to the result string and reduce its count and make a recursive call.

5 .To print only valid parentheses, make sure at any given point of time, close parentheses count is not less that open parentheses count because it means close parentheses has been printed with its respective open parentheses.

SOLUTIONS:

#include <stdio.h>
    long long int dp[100][100];
     long long int find(int i,int j)
    {
    if(i<0||j<0)return 0;
    if(i==0&&j==0)
    {
        dp[0][0]=1;
        return 1;
    }
    if(dp[i][j])
    return dp[i][j];
    long long int s=0;
    if(i>j)
    return 0;
    if(i>0)
    s+=find(i-1,j);
    if(j>0)
    s+=find(i,j-1);
    dp[i][j]=s;
    return s;
    }


     int main()
    {  


     int t;
    scanf("%d",&t);
     while(t--)
    {
    int n;
    scanf("%d",&n);
    if(n%2==0)
    {
        printf("%lld\n",find(n/2,n/2));
    }
    else
    {
        printf("0\n");
    }

    } 
    return 0;
    }

#include <bits/stdc++.h>
    using namespace std;
    long long int dp[100][100];
    long long int find(int i,int j)
    {
    if(i<0||j<0)return 0;
    if(i==0&&j==0)
    {
        dp[0][0]=1;
        return 1;
    }
    if(dp[i][j])
    return dp[i][j];
    long long int s=0;
    if(i<j)
    s+=find(i,j-1);
    if(i>0)
    s+=find(i-1,j);
    dp[i][j]=s;
    return s;
    }


     int main()
    {  


    int t;
    cin>>t;
     while(t--)
    {
    int n;
    cin>>n;
    if(n%2==0)
    {
        cout<<find(n/2,n/2)<<endl;
    }
    else
    {
        cout<<0<<endl;
    }

    } 
     return 0;
    }

import java.util.*;
    import java.io.*;
    class balpal { 
    static long binomialCoeff(int n, int k) 
    { 
        long res = 1; 
        if (k > n - k) 
            k = n - k; 
        for (int i = 0; i < k; ++i) { 
            res *= (n - i); 
            res /= (i + 1); 
        } 

        return res; 
    } 
    static long catalan(int n) 
    { 
        long c = binomialCoeff(2 * n, n); 
        return c / (n + 1); 
    } 
    static long findWays(int n) 
    { 
        if ((n & 1) != 0) 
            return 0; 
        return catalan(n / 2); 
    } 
    public static void main(String[] args) 
    { 
       Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
        System.out.println(findWays(n));} 
    } 
    } 

dp = [[0 for i in range(100)] for j in range(100)]

def find(i, j):
	
	if i < 0 or j < 0:
		return 0
	
	if i == 0 and j == 0:
		dp[0][0] = 1
		return 1
	
	if dp[i][j]:
		return dp[i][j]
	s = 0
	
	if i < j:
		s += find(i, j - 1)

	if i > 0:
		s += find(i - 1, j)

	dp[i][j] = s

	return s

for _ in range(int(input())):
	
	n = int(input())
	
	if n % 2 == 0:
		print(find(n // 2, n // 2))

	else:
		print(0)

[forminator_quiz id="2087"]

This article tried to discuss Recursion and Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion and Backtracking you can check out MYCODE | Competitive Programming.