Cargando editor...

Medium

In the village of Santa, there is a magic staircase that leads to the toy factory π§Έ. The elves, always looking to get exercise and have fun πββοΈ, decide to jump the steps of the staircase.

They give us `steps`

as the number of steps on the staircase and the maximum number of steps `maxJump`

that an elf can jump in a single jump.

Your task is to help the elves find **all the possible sequences of jumps they can make to go up the staircase, sorted from least to most**. Considering that the elves can jump at most `maxJump`

steps in a single jump (but they can jump fewer steps if they wish).

For example, if there is a staircase of `steps = 4`

and `maxJump = 2`

is the maximum number of steps that an elf can jump in a single jump, then there are five possible jumping sequences:

`[1, 1, 1, 1]`

(jumps 1 step 4 times)`[1, 1, 2]`

(jumps 1 step 2 times and then 2 steps)`[1, 2, 1]`

(jumps 1 step, then 2 steps and then 1 step)`[2, 1, 1]`

(jumps 2 steps, then 1 step and then 1 step)`[2, 2]`

(jumps 2 steps 2 times)

More examples:

```
getStaircasePaths(2, 1) // [[1, 1]]
getStaircasePaths(3, 3) // [[1, 1, 1], [1, 2], [2, 1], [3]]
getStaircasePaths(5, 1) // [[1, 1, 1, 1, 1]]
getStaircasePaths(5, 2)
/*
[
[1, 1, 1, 1, 1],
[1, 1, 1, 2],
[1, 1, 2, 1],
[1, 2, 1, 1],
[1, 2, 2],
[2, 1, 1, 1],
[2, 1, 2],
[2, 2, 1],
]
*/
```