We have:
n1
number of {}
brackets ,
n2
number of ()
brackets ,
n3
number of []
brackets ,
How many different valid combination of these brackets we can have?
What I thought: I wrote a brute force code in java (which comes in the following) and counted all possible combinations, I know it's the worst solution possible,
(the code is for general case in which we can have different types of brackets)
Any mathematical approach ?
Note 1: valid combination is defined as usual, e.g. {{()}}
: valid , {(}){}
: invalid
Note 2: let's assume that we have 2 pairs of {}
, 1 pair of ()
and 1 pair of []
, the number of valid combinations would be 168 and the number of all possible (valid & invalid) combinations would be 840
static void paranthesis_combination(char[] open , char[] close , int[] arr){
int l = 0;
for (int i = 0 ; i < arr.length ; i++)
l += arr[i];
l *= 2;
paranthesis_combination_sub(open , close , arr , new int[arr.length] , new int[arr.length], new StringBuilder(), l);
System.out.println(paran_count + " : " + valid_paran_count);
return;
}
static void paranthesis_combination_sub(char[] open , char[] close, int[] arr , int[] open_so_far , int[] close_so_far, StringBuilder strbld , int l){
if (strbld.length() == l && valid_paran(open , close , strbld)){
System.out.println(new String(strbld));
valid_paran_count++;
return;
}
for (int i = 0 ; i < open.length ; i++){
if (open_so_far[i] < arr[i]){
strbld.append(open[i]);
open_so_far[i]++;
paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l);
open_so_far[i]--;
strbld.deleteCharAt(strbld.length() -1 );
}
}
for (int i = 0 ; i < open.length ; i++){
if (close_so_far[i] < open_so_far[i]){
strbld.append(close[i]);
close_so_far[i]++;
paranthesis_combination_sub(open , close, arr , open_so_far , close_so_far, strbld , l);
close_so_far[i]--;
strbld.deleteCharAt(strbld.length() -1 );
}
}
return;
}