This is a recursive function to generate all possible n pairs of balanced parentheses for a given value of n<=20.
Input: 1 Output: {}
Input: 2 Output: {}{}
{{}}
What is the time complexity of the following code? Also, can it be done using Dynamic Programming?
# include<stdio.h>
# define MAX_SIZE 100
void printParenthesis(int pos, int n, int open, int close)
{
static char str[MAX_SIZE];
if(close == n)
{
printf("%s \n", str);
return;
}
else
{
if(open > close) {
str[pos] = '}';
printParenthesis(pos+1, n, open, close+1);
}
if(open < n) {
str[pos] = '{';
printParenthesis(pos+1, n, open+1, close);
}
}
}
/* driver program to test above functions */
int main()
{
int n;
scanf("%d", &n);
printParenthesis(0, n, 0, 0);
getchar();
return 0;
}
