Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.
1) Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
2) Count the number of possible Binary Search Trees with n keys (See this)
3) Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Recursive Solution
Catalan numbers satisfy the following recursive formula.
Following is the implementation of above recursive formula.
C++
#include<iostream>
using namespace std;
// A recursive function to find nth catalan number
unsigned long int catalan(unsigned int n)
{
// Base case
if (n <= 1) return 1;
// catalan(n) is sum of catalan(i)*catalan(n-i-1)
unsigned long int res = 0;
for (int i=0; i<n; i++)
res += catalan(i)*catalan(n-i-1);
return res;
}
// Driver program to test above function
int main()
{
for (int i=0; i<10; i++)
cout << catalan(i) << " ";
return 0;
}
Output :
1 1 2 5 14 42 132 429 1430 4862
The value of nth catalan number is exponential that makes the time complexity exponential.
[ad type=”banner”]
Dynamic Programming Solution
We can observe that the above recursive implementation does a lot of repeated work (we can the same by drawing recursion tree). Since there are overlapping subproblems, we can use dynamic programming for this. Following is a Dynamic programming based implementation in C++.
C++ Program
#include<iostream>
using namespace std;
// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
// Table to store results of subproblems
unsigned long int catalan[n+1];
// Initialize first two values in table
catalan[0] = catalan[1] = 1;
// Fill entries in catalan[] using recursive formula
for (int i=2; i<=n; i++)
{
catalan[i] = 0;
for (int j=0; j<i; j++)
catalan[i] += catalan[j] * catalan[i-j-1];
}
// Return last entry
return catalan[n];
}
// Driver program to test above function
int main()
{
for (int i = 0; i < 10; i++)
cout << catalanDP(i) << " ";
return 0;
}
Output:
1 1 2 5 14 42 132 429 1430 4862
Time Complexity: Time complexity of above implementation is O(n2)
[ad type=”banner”]
Using Binomial Coefficient
We can also use the below formula to find nth catalan number in O(n) time.
C++ Program
#include<iostream>
using namespace std;
// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n, unsigned int k)
{
unsigned long int res = 1;
// Since C(n, k) = C(n, n-k)
if (k > n - k)
k = n - k;
// Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
for (int i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
}
return res;
}
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
// Calculate value of 2nCn
unsigned long int c = binomialCoeff(2*n, n);
// return 2nCn/(n+1)
return c/(n+1);
}
// Driver program to test above functions
int main()
{
for (int i = 0; i < 10; i++)
cout << catalan(i) << " ";
return 0;
}
Output:
1 1 2 5 14 42 132 429 1430 4862
Time Complexity: Time complexity of above implementation is O(n).
We can also use below formula to find nth catalan number in O(n) time.
[ad type=”banner”]