Catalan Number

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.
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.
4. 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)