Stair Permutations Problem | Dataford Interview Questions

An Equinix Metal provisioning workflow advances through n ordered stages. Each transition may advance by exactly 1 or 2 stages. Given n, return every distinct ordered sequence of moves that reaches stage n exactly.

Sequences are permutations by order, so [1, 2] and [2, 1] are different when both are valid. Return the results in depth-first order, trying a 1-step move before a 2-step move. For n = 0, return [[]], representing the one valid sequence containing no moves.

Formal Specification

Implement stair_paths(n):

Input: An integer n, representing the destination stair.
Output: A list of lists of integers. Each inner list contains only 1 and 2, and its values sum to n.

Constraints

0 <= n <= 20
Each move is exactly 1 or 2
Return every valid sequence
Try a 1-step move before a 2-step move

Function Signature

def stair_paths(n):

Your question is Stair Permutations Problem. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem