The Grandest Staircase Of Them All

Origial Animation in CodePen.io

The Grandest Staircase Of Them All

Created: Oct 24, 2026

Last modified: Oct 24, 2026

TL, DR.

The Grandest Staircase Of Them All
==================================

With the LAMBCHOP doomsday device finished, Commander Lambda is preparing to debut on the galactic stage -- but in order to make a grand entrance, Lambda needs a grand staircase! As the Commander's personal assistant, you've been tasked with figuring out how to build the best staircase EVER.

Lambda has given you an overview of the types of bricks available, plus a budget. You can buy different amounts of the different types of bricks (for example, 3 little pink bricks, or 5 blue lace bricks). Commander Lambda wants to know how many different types of staircases can be built with each amount of bricks, so they can pick the one with the most options.

Each type of staircase should consist of 2 or more steps.  No two steps are allowed to be at the same height - each step must be lower than the previous one. All steps must contain at least one brick. A step's height is classified as the total amount of bricks that make up that step.
For example, when N = 3, you have only 1 choice of how to build the staircase, with the first step having a height of 2 and the second step having a height of 1: (# indicates a brick)

#
##
21

When N = 4, you still only have 1 staircase choice:

#
#
##
31

But when N = 5, there are two ways you can build a staircase from the given bricks. The two staircases can have heights (4, 1) or (3, 2), as shown below:

#
#
#
##
41

#
##
##
32

Write a function called solution(n) that takes a positive integer n and returns the number of different staircases that can be built from exactly n bricks. n will always be at least 3 (so you can have a staircase at all), but no more than 200, because Commander Lambda's not made of money!

Languages
=========

To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Java cases --
Input:
Solution.solution(3)
Output:
    1

Input:
Solution.solution(200)
Output:
    487067745

-- Python cases --
Input:
solution.solution(200)
Output:
    487067745

Input:
solution.solution(3)
Output:
    1

Commander Lambda wants a grand entrance, so we have to build staircases. We get n bricks and need to know how many different staircases we can make using all of them. The rules: at least two steps, every step has at least one brick, and each step is strictly lower than the one before it.

# Staircases are sums

Forget the bricks for a second and look at the heights. A staircase with 5 bricks and steps of 4 and 1 is just 5 = 4 + 1. Since the steps go strictly down, the heights are all different, and their order is already fixed (tallest first). So the question becomes: in how many ways can you write n as a sum of distinct numbers, using at least two of them? For 5 there are two: 4 + 1 and 3 + 2. In math these are called partitions into distinct parts.

# The obvious idea

Build them all: choose the tallest step, then build the rest of the staircase with fewer bricks and steps lower than that one, and count every staircase you finish. It's a nice recursion, and it works for small n. The problem is how many there are: with 200 bricks there are 487,067,745 staircases, and building them one by one is way too much work just to count them.

# One height at a time

Here's another way to look at it. Go through the possible step heights, 1, 2, 3…, one at a time, and for each one ask: does the staircase have a step of this height or not? A height can show up at most once, which is exactly what keeps the steps different. To count without building anything, we fill in a table:

m[i][j] is the number of ways to stack j bricks into steps of different heights, all of them between 1 and i.

No step of height i: you still need to place j bricks, now with heights up to i − 1. That's m[i-1][j], the cell right above.

A step of height i (only if it fits, j ≥ i): that step uses i bricks, and the remaining j − i go into lower steps. That's m[i-1][j-i], the cell above and i columns to the left.

m[i][j] = \begin{cases} m[i-1][j] + m[i-1][j-i] & j \ge i \\ m[i-1][j] & j < i \end{cases}

The starting point is m[0][0] = 1: with no heights at all there's exactly one way to place 0 bricks, which is placing nothing. Everything else in row 0 is 0, since there's no way to place bricks without heights. Along the way the table also counts piles with a single step, like 4 bricks as one step of height 4. Those aren't staircases, but the table needs them: in a later row, that 4 gets a 2 added and turns into 4 + 2. So where's the answer? In m[n-1][n]: n bricks with heights only up to n − 1. No step can hold all n bricks, so every pile in that cell has at least two steps, which is exactly what the statement asks for. That's why the table only needs rows 0 to n − 1: n rows and n + 1 columns.

# Filling it in, step by step

Here's the table for n = 6: rows 0 to 5, columns 0 to 6. Row 0 is the starting point, just as the code leaves it: m[0][0] = 1 and zeros. The other 35 cells get filled one per step, row by row and starting at column 0, in the same order as the two loops. Column 0 comes out all 1s on its own: a step of height i never fits in 0 bricks, so each of those cells just copies the one above. At each step the new cell lights up, along with the two it comes from: the dashed one right above (no step of height i) and the pink one (a step of height i), when it fits. Move the slider or press the button to watch it fill up on its own.

ji	0	1	2	3	4	5	6
0	1	0	0	0	0	0	0
1
2
3
4
5

Starting point: m[0][0] = 1 and the rest of row 0 is 0. Everything else is still to be filled.

# How many staircases?

Now pick any number of bricks, up to the statement's 200. The answer always shows up right away. Up to n = 9 you'll also see the whole table, with the answer in the last cell, and up to n = 13 every staircase drawn out (with 13 bricks there are already 17 of them).

Bricks (n)

m[4][5] = 2

Ways to stack 5 bricks into steps of different heights from 1 to 4. No step can hold all 5 bricks, so each one is a staircase with at least two steps.

ji	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	1	1	1	1	0	0
3	1	1	1	2	1	1
4	1	1	1	2	2	2

4 + 1

3 + 2

How the staircases are drawn

The count always comes from the table. The drawings come from a separate piece of code: a recursive search with backtracking. It picks the tallest step first, trying every height that still fits from the highest down to 1, and for each choice builds the rest of the staircase with the remaining bricks and steps strictly lower than that one. When no bricks are left, it has found a staircase; then it backs up and tries the next height. Some branches lead nowhere (with 5 bricks, a first step of 2 leaves only height 1 for the other 3 bricks), and those simply come back empty.

Since every step is lower than the one before, each staircase comes out exactly once and already sorted, with no duplicates to filter out. And starting with n − 1 as the limit means the single step of height n is never built. It's the obvious idea from the top of the page, so it only works while there are few staircases: that's why the demo stops drawing them at 13. The demo does it in C#; here's the same idea in Python:

def staircases(left, limit):
    """Every staircase with `left` bricks and steps no taller than `limit`, tallest step first."""
    if left == 0:
        yield []                      # all bricks placed: one staircase
        return
    for step in range(min(left, limit), 0, -1):
        # the rest of the staircase: fewer bricks, and strictly lower than this step
        for rest in staircases(left - step, step - 1):
            yield [step] + rest


# n - 1 as the first limit: a single step of n bricks is never built
print(list(staircases(5, 5 - 1)))    # [[4, 1], [3, 2]]

# The code

I have to confess that I couldn't solve this problem on my own. The code comes from rudisimo's google-foobar repository; I adapted it to my version of the challenge, which asked for a function called solution, and later trimmed its last row: the original fills one more row and returns m[n][n] - 1, which is the same number, since that extra row only adds the single step of height n. Understanding why it works is what made this page worth writing.

m is the table: n rows (heights up to n - 1) and n + 1 columns (0 to n bricks), so that index 0 means "no heights" and "0 bricks".

Each cell starts as the one above it (no step of height i) and, if i fits, adds the one above and i columns to the left (a step of height i).

It returns m[n-1][n]. With n = 200 that's about 40,000 cells, and the answer is instant.

def solution(n):
    m = [[0 for i in range(n + 1)] for j in range(n)]
    m[0][0] = 1
    for i in range(1, n):
        for j in range(0, n + 1):
            m[i][j] = m[i - 1][j]
            if j >= i:
                m[i][j] = m[i][j] + m[i - 1][j - i]
    return m[n - 1][n]

# Variant: a single row

Each row only reads from the row right above it, so there's no need to keep the whole table. One list is enough, updated in place, as long as you walk it backwards. When ways[j] adds ways[j - i], that cell hasn't been updated for i yet, so it still means "no step of height i". Walk it forwards and it would already include that step, so the same height could be used again and again: with n = 5 you'd get 6 instead of 2, because piles like 1 + 1 + 3 would sneak in.

def solution(n):
    # ways[j]: ways to stack j bricks with the heights seen so far
    ways = [1] + [0] * n
    # heights up to n - 1 only: every staircase ends up with at least two steps
    for i in range(1, n):
        # backwards, so ways[j - i] still doesn't include height i: each height is used at most once
        for j in range(n, i - 1, -1):
            ways[j] += ways[j - i]
    return ways[n]

# Wrapping up

The bricks were a disguise: underneath there's a classic counting problem. Once you see each height as a yes-or-no question (is there a step this tall?), it's the same pattern as the 0/1 knapsack, only counting instead of maximizing. And when a problem asks "how many ways", building every way is rarely the answer. Counting them through smaller subproblems usually is.