Hello Everyone,

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.

- Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
- Count the number of possible Binary Search Trees with n keys.
- 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.
- Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

**Recursive Solution**

Catalan numbers satisfy the following recursive formula.

Following is the implementation of above recursive formula.

`#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 code`

`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** of above implementation is equivalent to nth catalan number.

The value of nth catalan number is exponential that makes the time complexity exponential.

**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 .

`#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 code`

`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)