Number of balanced bracket subsequence of length 2 and 4 | C ++ implementation of above approach ; Taking the frequency suffix sum of the number of 2 's present after every index ; Storing the count of subsequence ; Subsequence of length 2 ; Subsequence of length 4 of type 1 1 2 2 ; Subsequence of length 4 of type 1 2 1 2 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void countWays ( int a [ ] , int n ) { int i , j ; long suff [ n ] ; if ( a [ n - 1 ] == 2 ) suff [ n - 1 ] = 1 ; for ( i = n - 2 ; i >= 0 ; i -- ) { if ( a [ i ] == 2 ) suff [ i ] = suff [ i + 1 ] + 1 ; else suff [ i ] = suff [ i + 1 ] ; } long ss = 0 ; for ( i = 0 ; i < n ; i ++ ) { if ( a [ i ] == 1 ) ss += suff [ i ] ; } for ( i = 0 ; i < n ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { if ( a [ i ] == 1 && a [ j ] == 1 && suff [ j ] >= 2 ) { ss += ( suff [ j ] ) * ( suff [ j ] - 1 ) / 2 ; } } } for ( i = 0 ; i < n ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { if ( a [ i ] == 1 && a [ j ] == 1 && ( suff [ i ] - suff [ j ] ) >= 1 && suff [ j ] >= 1 ) { ss += ( suff [ i ] - suff [ j ] ) * suff [ j ] ; } } } cout << ( ss ) ; } int main ( ) { int a [ ] = { 1 , 2 , 1 , 1 , 2 , 2 } ; int n = 6 ; countWays ( a , n ) ; return 0 ; }