Number of entries in every line is equal to line number. For example, the first line has “1″, the second line has “1 1″, the third line has “1 2 1″,.. and so on. Every entry in a line is value of a Binomial Coefficient. The value of ith entry in line number line is C(line, i). The value can be calculated using following formula.
// A simple O(n^3) program for Pascal’s Triangle
#include <stdio.h>
int binomialCoeff(int n, int k);
// Function to print first n lines of Pascal’s Triangle
void printPascal(int n)
{
// Iterate through every line and print entries in it
for (int line = 1; line < n; line++)
{
// Every line has number of integers equal to line number
for (int i = 1; i <= line; i++)
printf(“%d “, binomialCoeff(line, i));
printf(“\n”);
}
}
int binomialCoeff(int n, int k)
{
int res = 1;
if (k > n – k)
k = n – k;
for (int i = 0; i < k; ++i)
{
res *= (n – i);
res /= (i + 1);
}
return res;
}
// Driver program to test above function
int main()
{
int n = 7;
printPascal(n);
return 0;
}

Method 2( O(n^2) time and O(n^2) extra space )
If we take a closer at the triangle, we observe that every entry is sum of the two values above it. So we can create a 2D array that stores previously generated values. To generate a value in a line, we can use the previously stored values from array.
// A O(n^2) time and O(n^2) extra space method for Pascal’s Triangle
void printPascal(int n)
{
int arr[n][n]; // An auxiliary array to store generated pscal triangle values
// Iterate through every line and print integer(s) in it
for (int line = 0; line < n; line++)
{
// Every line has number of integers equal to line number
for (int i = 0; i <= line; i++)
{
// First and last values in every row are 1
if (line == i  i == 0)
arr[line][i] = 1;
else // Other values are sum of values just above and left of above
arr[line][i] = arr[line1][i1] + arr[line1][i];
printf(“%d “, arr[line][i]);
}
printf(“\n”);
}
}

Method 3 ( O(n^2) time and O(1) extra space )
This method is based on method 1. We know that ith entry in a line number line is Binomial CoefficientC(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i1). It can be calculated in O(1) time using the following.
// A O(n^2) time and O(1) extra space function for Pascal’s Triangle
void printPascal(int n)
{
for (int line = 1; line <= n; line++)
{
int C = 1; // used to represent C(line, i)
for (int i = 1; i <= line; i++)
{
printf(“%d “, C); // The first value in a line is always 1
C = C * (line – i) / i; // C(line, i) = C(line, i1) * (line – i) / i
}
printf(“\n”);
}
}
