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.
[pastacode lang=”cpp” manual=”%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20recursive%20function%20to%20find%20nth%20catalan%20number%0Aunsigned%20long%20int%20catalan(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20if%20(n%20%3C%3D%201)%20return%201%3B%0A%20%0A%20%20%20%20%2F%2F%20catalan(n)%20is%20sum%20of%20catalan(i)*catalan(n-i-1)%0A%20%20%20%20unsigned%20long%20int%20res%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20res%20%2B%3D%20catalan(i)*catalan(n-i-1)%3B%0A%20%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3C10%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalan(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++” highlight=”” provider=”manual”/]
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++.
[pastacode lang=”cpp” manual=”%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20dynamic%20programming%20based%20function%20to%20find%20nth%0A%2F%2F%20Catalan%20number%0Aunsigned%20long%20int%20catalanDP(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Table%20to%20store%20results%20of%20subproblems%0A%20%20%20%20unsigned%20long%20int%20catalan%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20first%20two%20values%20in%20table%0A%20%20%20%20catalan%5B0%5D%20%3D%20catalan%5B1%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20entries%20in%20catalan%5B%5D%20using%20recursive%20formula%0A%20%20%20%20for%20(int%20i%3D2%3B%20i%3C%3Dn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20catalan%5Bi%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20for%20(int%20j%3D0%3B%20j%3Ci%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20catalan%5Bi%5D%20%2B%3D%20catalan%5Bj%5D%20*%20catalan%5Bi-j-1%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Return%20last%20entry%0A%20%20%20%20return%20catalan%5Bn%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalanDP(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D%0A” message=”C++ Program ” highlight=”” provider=”manual”/]
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.
[pastacode lang=”cpp” manual=”%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20value%20of%20Binomial%20Coefficient%20C(n%2C%20k)%0Aunsigned%20long%20int%20binomialCoeff(unsigned%20int%20n%2C%20unsigned%20int%20k)%0A%7B%0A%20%20%20%20unsigned%20long%20int%20res%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Since%20C(n%2C%20k)%20%3D%20C(n%2C%20n-k)%0A%20%20%20%20if%20(k%20%3E%20n%20-%20k)%0A%20%20%20%20%20%20%20%20k%20%3D%20n%20-%20k%3B%0A%20%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%20%5Bn*(n-1)*—*(n-k%2B1)%5D%20%2F%20%5Bk*(k-1)*—*1%5D%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20k%3B%20%2B%2Bi)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20res%20*%3D%20(n%20-%20i)%3B%0A%20%20%20%20%20%20%20%20res%20%2F%3D%20(i%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20A%20Binomial%20coefficient%20based%20function%20to%20find%20nth%20catalan%0A%2F%2F%20number%20in%20O(n)%20time%0Aunsigned%20long%20int%20catalan(unsigned%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Calculate%20value%20of%202nCn%0A%20%20%20%20unsigned%20long%20int%20c%20%3D%20binomialCoeff(2*n%2C%20n)%3B%0A%20%0A%20%20%20%20%2F%2F%20return%202nCn%2F(n%2B1)%0A%20%20%20%20return%20c%2F(n%2B1)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20catalan(i)%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]
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”]