Problem Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses. OR Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Follow up Make sure the returned list of strings are sorted. Examples Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] ...
What Catalan numbers form a sequence of natural numbers with applications in various combinatorial mathematics problems. They can be defined in several ways and appear in problems involving balanced parentheses, binary search trees, and more. More on wiki. The (n)-th Catalan number can be given by the formula: $$ C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!} $$ Some common properties of Catalan numbers include: They count the number of expressions containing (n) pairs of correctly matched parentheses. See - Generate Parentheses Problem. They count the number of rooted binary trees with (n + 1) leaves. They count the number of ways to completely parenthesise (n+1) factors in a product. Application of Catalan Number Algorithm The number of ways to stack coins on a base row of (n) consecutive coins in a plane, where no coins can be placed on the two sides of the bottom row and every additional coin must lie above two other coins, is given by the (n)th Catalan number. The number of ways to correctly group a string of (n) pairs of parentheses, ensuring each open parenthesis matches with a closing one, corresponds to the (n)th Catalan number. The number of ways to divide a convex polygon with (n+2) sides into triangles by drawing non-intersecting, straight lines between vertices is determined by the (n)th Catalan number, an application that interested Euler. Solution Method 1 - Recursion Just follow the recursive definition of Catalan numbers: $$ C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} $$ ...