Editor

Every Way Up the Stairs

#611 · Recursion and backtracking · Advanced · Find and fix · 115 XP · about 18 min

You climb a staircase of n steps, taking 1 or 2 steps at a time. step_patterns(n) should return every possible way up as a list of lists, where each inner list holds the step sizes in order, such as [1, 2, 1]. The patterns come in sorted order (the order sorted() would put them in). For n = 0 the only pattern is the empty one, so the answer is [[]].

The code in the editor has a bug. The number of patterns is right (len(step_patterns(4)) is 5), but every pattern in the result is an empty list.

Examples

step_patterns(3)  # returns [[1, 1, 1], [1, 2], [2, 1]]
step_patterns(2)  # returns [[1, 1], [2]]
step_patterns(0)  # returns [[]]

Constraints

  • 0 <= n <= 20

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.