Given a positive integer n, we want to generate all n possible combinations of open and closed brackets while we should always match all open brackets with a closed bracket.
Example:
If n = 1: then display ()
If n=2: then display () (), (())
If n=3: then display ((())) , (()()), (())(), ()(()), ()()()
Solution:
This is a typical candidate for dynamic programming using recursion.
Basically we will have mainly two variables that we keep track in each recursion in terms of how many open or closed bracket we append so far.
Beginning will keep track the opening brackets for each valid parenthesis we are going to generate (eg ((())) )
Ending will keep track from closing brackets for each valid parenthesis we are going to generate (eg ((())) )
In each recursion, we will append “(” and decrease the beginning pointer and append “)” and decrease the ending parenthesis to eventually check if we ran out of both of them and when we do we copy the generated string to our list.
class GenerateBracketN {
public static void Main() {
List<string> list = new List<string>();
int n = 10;
Generate(list, n,n, new char[2*n], 0);
int a = 0;
}
static void Generate(List<string> list, int begining, int ending, char[] str, int index) {
if (begining < 0 || ending < begining) return; //exit cond
if (ending == 0 && begining == 0) //base
list.Add(new string(str));
else {
str[index] = '(';
Generate(list, begining - 1, ending, str, index + 1);
str[index] = ')';
Generate(list, begining, ending - 1, str, index + 1);
}
}