Skip to main content

Catalan's triangle

Here given code implementation process.

// C Program for
// Catalan's triangle
#include <stdio.h>

void catalansTriangle(int n)
{
	if (n <= 0)
	{
		return;
	}
	// Optimize N *N space by using 2 rows
	int dp[2][n + 1];
	// Set initial value of first column
	dp[0][0] = 1;
	dp[1][0] = 1;
	// We can solve this problem only use two rows
	// So initial select second row which position is 1
	int row = 1;
	for (int i = 1; i <= n; ++i)
	{
		// Set initial value in current column
		dp[0][i] = 0;
		dp[1][i] = 0;
		for (int j = 0; j < i; ++j)
		{
			if (j > 0)
			{
				if (j + 1 == i)
				{
					// When last element
					dp[row][j] = dp[row][j - 1];
				}
				else if (row == 1)
				{
					// Change second row 'j' column value
					dp[row][j] = dp[0][j] + dp[row][j - 1];
				}
				else
				{
					// Change first row 'j' column value
					dp[row][j] = dp[1][j] + dp[row][j - 1];
				}
			}
			// Print element value
			printf("  %d", dp[row][j]);
		}
		// Include new line
		printf("\n");
		// Change the row
		if (row == 1)
		{
			row = 0;
		}
		else
		{
			row = 1;
		}
	}
}
int main()
{
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	catalansTriangle(9);
	return 0;
}

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
// Java program for
// Catalan's triangle
public class Triangle
{
	public void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int[][] dp = new int[2][n + 1];
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				System.out.print(" " + dp[row][j]);
			}
			// Include new line
			System.out.print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Catalan's triangle
class Triangle
{
	public: void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int dp[2][n + 1];
      
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
      
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
      
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0][i] = 0;
			dp[1][i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				cout << " " << dp[row][j];
			}
			// Include new line
			cout << "\n";
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
};
int main()
{
	Triangle *task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task->catalansTriangle(9);
	return 0;
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Include namespace system
using System;
// Csharp program for
// Catalan's triangle
public class Triangle
{
	public void catalansTriangle(int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		int[,] dp = new int[2,n + 1];
		// Set initial value of first column
		dp[0,0] = 1;
		dp[1,0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		int row = 1;
		for (int i = 1; i <= n; ++i)
		{
			// Set initial value in current column
			dp[0,i] = 0;
			dp[1,i] = 0;
			for (int j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row,j] = dp[row,j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row,j] = dp[0,j] + dp[row,j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row,j] = dp[1,j] + dp[row,j - 1];
					}
				}
				// Print element value
				Console.Write(" " + dp[row,j]);
			}
			// Include new line
			Console.Write("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
	public static void Main(String[] args)
	{
		Triangle task = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
package main
import "fmt"
// Go program for
// Catalan's triangle

func catalansTriangle(n int) {
	if n <= 0 {
		return
	}
	// Optimize N *N space by using 2 rows
	var dp = make([][] int, 2)
	for i:= 0; i < 2; i++{
		dp[i] = make([]int,n+1)
	}
	// Set initial value of first column
	dp[0][0] = 1
	dp[1][0] = 1
	// We can solve this problem only use two rows
	// So initial select second row which position is 1
	var row int = 1
	for i := 1 ; i <= n ; i++ {
		for j := 0 ; j < i ; j++ {
			if j > 0 {
				if j + 1 == i {
					// When last element
					dp[row][j] = dp[row][j - 1]
				} else if row == 1 {
					// Change second row 'j' column value
					dp[row][j] = dp[0][j] + dp[row][j - 1]
				} else {
					// Change first row 'j' column value
					dp[row][j] = dp[1][j] + dp[row][j - 1]
				}
			}
			// Print element value
			fmt.Print(" ", dp[row][j])
		}
		// Include new line
		fmt.Print("\n")
		// Change the row
		if row == 1 {
			row = 0
		} else {
			row = 1
		}
	}
}
func main() {

	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	catalansTriangle(9)
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
<?php
// Php program for
// Catalan's triangle
class Triangle
{
	public	function catalansTriangle($n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		$dp = array_fill(0, 2, array_fill(0, $n + 1, 0));
		// Set initial value of first column
		$dp[0][0] = 1;
		$dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		$row = 1;
		for ($i = 1; $i <= $n; ++$i)
		{
			for ($j = 0; $j < $i; ++$j)
			{
				if ($j > 0)
				{
					if ($j + 1 == $i)
					{
						// When last element
						$dp[$row][$j] = $dp[$row][$j - 1];
					}
					else if ($row == 1)
					{
						// Change second row 'j' column value
						$dp[$row][$j] = $dp[0][$j] + $dp[$row][$j - 1];
					}
					else
					{
						// Change first row 'j' column value
						$dp[$row][$j] = $dp[1][$j] + $dp[$row][$j - 1];
					}
				}
				// Print element value
				echo(" ".$dp[$row][$j]);
			}
			// Include new line
			echo("\n");
			// Change the row
			if ($row == 1)
			{
				$row = 0;
			}
			else
			{
				$row = 1;
			}
		}
	}
}

function main()
{
	$task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	$task->catalansTriangle(9);
}
main();

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Node JS program for
// Catalan's triangle
class Triangle
{
	catalansTriangle(n)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row = 1;
		for (var i = 1; i <= n; ++i)
		{
			for (var j = 0; j < i; ++j)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				process.stdout.write(" " + dp[row][j]);
			}
			// Include new line
			process.stdout.write("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
		}
	}
}

function main()
{
	var task = new Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}
main();

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
#  Python 3 program for
#  Catalan's triangle
class Triangle :
	def catalansTriangle(self, n) :
		if (n <= 0) :
			return
		
		#  Optimize N *N space by using 2 rows
		dp = [[0] * (n + 1) for _ in range(2) ]
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select second row which position is 1
		row = 1
		i = 1
		while (i <= n) :
			j = 0
			while (j < i) :
				if (j > 0) :
					if (j + 1 == i) :
						#  When last element
						dp[row][j] = dp[row][j - 1]
					elif (row == 1) :
						#  Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1]
					else :
						#  Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1]
					
				
				#  Print element value
				print(" ", dp[row][j], end = "")
				j += 1
			
			#  Include new line
			print(end = "\n")
			#  Change the row
			if (row == 1) :
				row = 0
			else :
				row = 1
			
			i += 1
		
	

def main() :
	task = Triangle()
	#  1
	#  1  1
	#  1  2  2
	#  1  3  5  5
	#  1  4  9  14  14
	#  1  5  14  28  42  42
	#  1  6  20  48  90  132  132
	#  1  7  27  75  165  297  429  429
	#  1  8  35  110  275  572  1001  1430  1430
	#  --------------------------------------------
	#  Catalan's triangle when row = 9
	task.catalansTriangle(9)

if __name__ == "__main__": main()

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
#  Ruby program for
#  Catalan's triangle
class Triangle 
	def catalansTriangle(n) 
		if (n <= 0) 
			return
		end

		#  Optimize N *N space by using 2 rows
		dp = Array.new(2) {Array.new(n + 1) {0}}
		#  Set initial value of first column
		dp[0][0] = 1
		dp[1][0] = 1
		#  We can solve this problem only use two rows
		#  So initial select second row which position is 1
		row = 1
		i = 1
		while (i <= n) 
			j = 0
			while (j < i) 
				if (j > 0) 
					if (j + 1 == i) 
						#  When last element
						dp[row][j] = dp[row][j - 1]
					elsif (row == 1) 
						#  Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1]
					else
 
						#  Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1]
					end

				end

				#  Print element value
				print(" ", dp[row][j])
				j += 1
			end

			#  Include new line
			print("\n")
			#  Change the row
			if (row == 1) 
				row = 0
			else
 
				row = 1
			end

			i += 1
		end

	end

end

def main() 
	task = Triangle.new()
	#  1
	#  1  1
	#  1  2  2
	#  1  3  5  5
	#  1  4  9  14  14
	#  1  5  14  28  42  42
	#  1  6  20  48  90  132  132
	#  1  7  27  75  165  297  429  429
	#  1  8  35  110  275  572  1001  1430  1430
	#  --------------------------------------------
	#  Catalan's triangle when row = 9
	task.catalansTriangle(9)
end

main()

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Scala program for
// Catalan's triangle
class Triangle()
{
	def catalansTriangle(n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
		// Set initial value of first column
		dp(0)(0) = 1;
		dp(1)(0) = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp(row)(j) = dp(row)(j - 1);
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp(row)(j) = dp(0)(j) + dp(row)(j - 1);
					}
					else
					{
						// Change first row 'j' column value
						dp(row)(j) = dp(1)(j) + dp(row)(j - 1);
					}
				}
				// Print element value
				print(" " + dp(row)(j));
				j += 1;
			}
			// Include new line
			print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Triangle = new Triangle();
		/*
		  1
		  1  1
		  1  2  2
		  1  3  5  5
		  1  4  9  14  14
		  1  5  14  28  42  42
		  1  6  20  48  90  132  132
		  1  7  27  75  165  297  429  429
		  1  8  35  110  275  572  1001  1430  1430
		  --------------------------------------------
		  Catalan's triangle when row = 9
		*/
		task.catalansTriangle(9);
	}
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430
// Swift 4 program for
// Catalan's triangle
class Triangle
{
	func catalansTriangle(_ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: n + 1), count: 2);
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				print(" ", dp[row][j], terminator: "");
				j += 1;
			}
			// Include new line
			print(terminator: "\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
func main()
{
	let task: Triangle = Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}
main();

Output

  1
  1  1
  1  2  2
  1  3  5  5
  1  4  9  14  14
  1  5  14  28  42  42
  1  6  20  48  90  132  132
  1  7  27  75  165  297  429  429
  1  8  35  110  275  572  1001  1430  1430
// Kotlin program for
// Catalan's triangle
class Triangle
{
	fun catalansTriangle(n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Optimize N *N space by using 2 rows
		var dp: Array < Array < Int >> = Array(2)
		{
			Array(n + 1)
			{
				0
			}
		};
		// Set initial value of first column
		dp[0][0] = 1;
		dp[1][0] = 1;
		// We can solve this problem only use two rows
		// So initial select second row which position is 1
		var row: Int = 1;
		var i: Int = 1;
		while (i <= n)
		{
			var j: Int = 0;
			while (j < i)
			{
				if (j > 0)
				{
					if (j + 1 == i)
					{
						// When last element
						dp[row][j] = dp[row][j - 1];
					}
					else if (row == 1)
					{
						// Change second row 'j' column value
						dp[row][j] = dp[0][j] + dp[row][j - 1];
					}
					else
					{
						// Change first row 'j' column value
						dp[row][j] = dp[1][j] + dp[row][j - 1];
					}
				}
				// Print element value
				print(" " + dp[row][j]);
				j += 1;
			}
			// Include new line
			print("\n");
			// Change the row
			if (row == 1)
			{
				row = 0;
			}
			else
			{
				row = 1;
			}
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Triangle = Triangle();
	/*
	  1
	  1  1
	  1  2  2
	  1  3  5  5
	  1  4  9  14  14
	  1  5  14  28  42  42
	  1  6  20  48  90  132  132
	  1  7  27  75  165  297  429  429
	  1  8  35  110  275  572  1001  1430  1430
	  --------------------------------------------
	  Catalan's triangle when row = 9
	*/
	task.catalansTriangle(9);
}

Output

 1
 1 1
 1 2 2
 1 3 5 5
 1 4 9 14 14
 1 5 14 28 42 42
 1 6 20 48 90 132 132
 1 7 27 75 165 297 429 429
 1 8 35 110 275 572 1001 1430 1430




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment