## Print the kth row of a Pascal Triangle

Pascal Triangle is an arrangement of numbers in rows resembling a triangle. Here, our task is to print the k^{th} row for which the integer k is provided.

Remember that in a Pascal Triangle the indexing of rows starts from 0. Let's see how the output should look like:

Input: 3

Output: 1 3 3 1

Input: 4

Output: 1 4 6 4 1

Input: 2

Output: 1 2 1

Input: 0

Output: 1

Here, we are going to see two methods for this algorithm:

- Recursion Method
- Using the

formula but in a modified way(Time Complexity: O(n) and Auxiliary Space: O(1))^{n}C_{k}

*It is recommended to have a page and pen ready to understand the working of the algorithm.*

### Approach 1: Recursion Method

Pascal Triangle has a property that elements of a current row can be found with the help of the elements of the previous row. The value at each position of the Pascal Triangle is the direct sum of the above two values. Still didn't get it? Look at the image below:

The formula to find the value of the current row from the previous row is:

**curr_row = prev_row[i - 1] + prev_row[I]**

Example:

prev_row = [1, 2, 1]

curr_row[1] --------- initially storing 1

Using a `for `

loop from `1 to len(prev_row)`

curr_row = prev_row[1 - 1] + prev_row[1] = [1, 3]

curr_row = prev_row[2 - 1] + prev_row[2] = [1, 3, 3]

curr_row = [1, 3, 3, 1]--------------manually appending 1 at end of for loop

Now, we can use this property to find elements of any row, If we are given the value of `k `

that is the row number, we will find the elements of its previous row that `(k-1)`

^{th} row using the **recursion **method. Once we get the values of the previous row, we can use the above property and find the values of the `k`

^{th} row. Let's see how we can achieve this using recursion. It is suggested to learn how recursion works before moving ahead here.

Suppose k = 3, values of row 3 are to be printed(remember that row number starts from 0). Recursion will happen `k`

number of times. Let's see how:

We will stop the recursion when we reach the value of `k == 0`

. Now, at each stage, we will return the value of each row calculated with the formula discussed above. For your understanding the pictorial representation will look like this:

Now let's see the actual implementation of the Recursion approach in Python:

- Python

```
def find_row(k):
my_row = []
my_row.append(1) # since every row has its first value as 1
if k == 0:
return my_row
prev_row = find_row(k - 1) # recursively calling the previous row
for i in range(1, len(prev_row)):
curr_row = prev_row[i - 1] + prev_row[i] # formula to calculate the value of current row from previous row
my_row.append(curr_row)
my_row.append(1) # since every row has its last value as 1
return my_row
k = 6
arr = find_row(k)
for i in arr:
print(i, end=" ")<br/>
```

1 3 3 1

1. We can see in the above code, the function `find_row()`

is recursively called until `k == 0`

which is our base condition to stop the recursion.

2. We are storing the list in the array `my_row[]`

and every time we need to do `my_row.append(1)`

since the first and the last value of each row is 1.

3. Note that after every recursion step, we are storing the array in prev_row for calculating the values in the further steps.

### Approach 2: Using ^{n}C_{k} formula in a modified way (Time Complexity: O(n) and Auxiliary Space: O(1))

We should know in a Pascal Triangle, every single element of each row is calculated by a formula of **Combinations **which is commonly known as **"n choose k"** or the number of combinations of k elements from n elements. The formula is:

Note: **"n choose k"** can also be written` C(n,k)`

,` `

or even^{n}C_{k}` `

. ^{n}C_{k}

The value at each position of Pascal Triangle using the

formula is shown below where^{n}C_{k}

`n`

= current row number

`k`

= current column number

We can use this formula in our algorithm and find the values of the given row. But calculating

each time increases the time complexity. Also, ^{n}C_{k}`n!`

may overflow for larger values of n. So, we can modify the

formula and come up with an efficient solution. Let's see how:^{n}C_{k}

For a detailed explanation of this formula please click here.

So basically for this approach, we are going to generate the values only for the particular row and not for the previous rows as we did in the earlier approach. Let's see how to achieve it:

```
def find_row(n):
prev_val = 1 # first value is always 1
print(prev_val, end = ' ')
for k in range(1, n + 1):
curr_val = (prev_val * (n - k + 1)) // k # using the formula nCk = (nCk-1 * (n - k + 1))/k
print(curr_val, end=' ')
prev_val = curr_val
# Driver code
n = 0
find_row(n)
```

So, we have a function `find_row()`

to generate the values of the given row.

1. `prev_value`

is initialized to `1`

as every row has its first value as `1`

.

2. Note that the` prev_value`

will always store the preceding value of the same row which will be helpful to calculate the current value. That is `prev_value`

stores `C(n, k-1)`

3. We will use the `for `

loop to generate each value of the row. So it ranges from `1 to n+1`

.

4. In the `for `

loop, we use the formula discussed above to generate the values.

For better understanding, first, use the original

formula and try to get the values, and then go for the modified formula.^{n}C_{k}