Code-golf generate pascal's triangle

code-golf

programming

pascal's triangle

algorithms

competitive programming

Code-golf generate pascal's triangle

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Pascal's Triangle is a triangular array where each number is the sum of the two numbers directly above it. The first and last elements of every row are 1. It encodes binomial coefficients — row n, position k equals C(n,k). In code-golf, the challenge is to generate it in the fewest characters. Beyond golf, understanding the algorithm is useful because Pascal's Triangle appears in combinatorics, probability, polynomial expansion, and fractal patterns.

The Triangle

1Row 0:           1
2Row 1:          1 1
3Row 2:         1 2 1
4Row 3:        1 3 3 1
5Row 4:       1 4 6 4 1
6Row 5:      1 5 10 10 5 1
7Row 6:     1 6 15 20 15 6 1

Each interior value is the sum of the two values above it: triangle[n][k] = triangle[n-1][k-1] + triangle[n-1][k].

Python: Standard Implementation

python

1def pascals_triangle(n):
2    triangle = []
3    for i in range(n):
4        row = [1]
5        if triangle:
6            last_row = triangle[-1]
7            row += [last_row[j] + last_row[j + 1] for j in range(len(last_row) - 1)]
8            row.append(1)
9        triangle.append(row)
10    return triangle
11
12for row in pascals_triangle(7):
13    print(row)
14# [1]
15# [1, 1]
16# [1, 2, 1]
17# [1, 3, 3, 1]
18# [1, 4, 6, 4, 1]
19# [1, 5, 10, 10, 5, 1]
20# [1, 6, 15, 20, 15, 6, 1]

This builds each row by summing adjacent pairs from the previous row and adding 1s at both ends.

Python: Code-Golf Solutions

python

1# 62 bytes — list-based
2def f(n):
3 r=[1]
4 for _ in range(n):print(r);r=[1]+[a+b for a,b in zip(r,r[1:])]+[1]
5
6f(6)
7
8# 56 bytes — using map and zip
9def f(n):
10 r=[1]
11 for _ in range(n):print(r);r=list(map(sum,zip([0]+r,r+[0])))
12
13f(6)
14
15# One-liner with reduce
16from functools import reduce
17print(*reduce(lambda a,_:[1]+[x+y for x,y in zip(a,a[1:])]+[1],range(6),[[1]]),sep='\n')

The zip([0]+r, r+[0]) trick pads the row with zeros on each side, so summing pairs naturally produces the next row including the boundary 1s.

JavaScript Solutions

javascript

1// Readable version
2function pascalsTriangle(n) {
3    const result = [[1]];
4    for (let i = 1; i < n; i++) {
5        const prev = result[i - 1];
6        const row = [1];
7        for (let j = 1; j < prev.length; j++) {
8            row.push(prev[j - 1] + prev[j]);
9        }
10        row.push(1);
11        result.push(row);
12    }
13    return result;
14}
15
16console.log(pascalsTriangle(7));
17
18// Golfed — 78 bytes
19f=n=>{r=[1];for(;n--;)console.log(r),r=[...r.map((v,i)=>v+(r[i+1]||0)),0].map((v,i)=>i?v:1)}

Using Math (Binomial Coefficients)

python

1from math import comb
2
3def pascals_math(n):
4    for i in range(n):
5        row = [comb(i, k) for k in range(i + 1)]
6        print(row)
7
8pascals_math(7)
9# [1]
10# [1, 1]
11# [1, 2, 1]
12# [1, 3, 3, 1]
13# ...

math.comb(n, k) directly computes binomial coefficients. This is clean but slower than the iterative approach for large triangles because each comb call is independent.

Recursive Approach

python

1def pascal_recursive(n):
2    if n == 0:
3        return [[1]]
4    prev = pascal_recursive(n - 1)
5    last = prev[-1]
6    new_row = [1] + [last[i] + last[i + 1] for i in range(len(last) - 1)] + [1]
7    return prev + [new_row]
8
9for row in pascal_recursive(6):
10    print(row)

The recursive version builds the triangle top-down. It is elegant but hits Python's recursion limit for large n (default 1000).

Applications of Pascal's Triangle

python

1from math import comb
2
3# 1. Binomial expansion: (a + b)^n
4# Coefficients of (x + 1)^4 = 1x^4 + 4x^3 + 6x^2 + 4x + 1
5n = 4
6coefficients = [comb(n, k) for k in range(n + 1)]
7print(coefficients)  # [1, 4, 6, 4, 1]
8
9# 2. Counting paths in a grid
10# Paths from top-left to (m, n) in a grid = C(m+n, n)
11m, n = 3, 4
12paths = comb(m + n, n)
13print(f"Paths in {m}x{n} grid: {paths}")  # 35
14
15# 3. Probability (coin flips)
16# Probability of exactly k heads in n flips
17n_flips = 5
18for k in range(n_flips + 1):
19    prob = comb(n_flips, k) / 2**n_flips
20    print(f"P({k} heads) = {prob:.4f}")

Pretty Printing

python

1def pretty_pascal(n):
2    triangle = []
3    row = [1]
4    for _ in range(n):
5        triangle.append(row)
6        row = [1] + [row[i] + row[i + 1] for i in range(len(row) - 1)] + [1]
7
8    width = len(' '.join(map(str, triangle[-1])))
9    for row in triangle:
10        print(' '.join(map(str, row)).center(width))
11
12pretty_pascal(7)
13#              1
14#             1 1
15#            1 2 1
16#           1 3 3 1
17#          1 4 6 4 1
18#        1 5 10 10 5 1
19#       1 6 15 20 15 6 1

Common Pitfalls

Off-by-one in row count: Some implementations count rows starting from 0 (row 0 = [1]), others from 1. Clarify whether n means "n rows" or "rows 0 through n" to avoid generating one too many or too few rows.
Not handling n=0: An empty triangle (0 rows) should return an empty list, not [[1]]. Always handle the edge case where no rows are requested.
Integer overflow in other languages: Pascal's Triangle values grow as C(n, n/2), which reaches billions by row 34. In C/C++ or Java, use long or BigInteger for rows beyond 30.
Modifying the previous row in place: When building a new row from the previous one, modifying the previous row during iteration produces incorrect results. Always read from the old row and write to a new one.
zip() truncating to shorter list: In zip([0]+r, r+[0]), both lists have the same length. But if you mistakenly use zip(r, r[1:]), the result is one element shorter than needed, missing the trailing 1.

Summary

Pascal's Triangle row n contains binomial coefficients C(n, 0) through C(n, n)
Build each row by summing adjacent pairs from the previous row: new[k] = old[k-1] + old[k]
The zip([0]+r, r+[0]) pattern is the most concise iterative approach in Python
Use math.comb(n, k) for direct computation of individual values
Pascal's Triangle appears in binomial expansion, grid path counting, and probability
For code-golf, the padding-with-zeros approach produces the shortest Python solution