#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.
step_patterns(3) # returns [[1, 1, 1], [1, 2], [2, 1]] step_patterns(2) # returns [[1, 1], [2]] step_patterns(0) # returns [[]]
0 <= n <= 20First solves only, ranked by stars and then time.