def triangle(n):
    if n == 0:
            return []
    if n == 1:
            return [[1]]
    if n == 2:
            return [[1], [1, 1]]

    prev_triangle = triangle(n - 1)
    prev_row = prev_triangle[-1]
    row = []
    row.append(1)
    for i in range(1, n - 1):
        pos = prev_row[i] + prev_row[i + 1]
        row.append(pos)
    row.append(1)
    prev_triangle.append(row)
    return prev_triangle