Найти все пути вниз по лестнице?

В интервью мне дали следующую задачу:

Учитывая лестницу с N ступенями, вы можете подниматься на 1 или 2 ступеньки каждый раз. Выведите все возможные пути снизу вверх.

Например:

N = 3

Output :
1 1 1
1 2
2 1

На собеседовании я просто сказал использовать динамическое программирование.

S (n) = S (n-1) +1 или S ( n) = S (n-1) +2

Однако во время интервью я написал для этого не очень хороший код. Как бы вы запрограммировали решение этой проблемы?

Большое спасибо!