Get Stair Paths

 1. You are given a number n representing number of stairs in a staircase.

2. You are standing at the bottom of staircase. You are allowed to climb 1 step, 2 steps or 3 steps in one move.
3. Complete the body of getStairPaths function - without changing signature - to get the list of all paths that can be used to climb the staircase up.
Use sample input and output to take idea about output.

Input Format

A number n

Output Format

Contents of the arraylist containing paths as shown in sample output

Constraints
0 <= n <= 10
Sample Input
3
Sample Output
[111, 12, 21, 3]

Solution:

import java.io.*;

import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        ArrayList<String> res = getStairPaths(n);

        System.out.println(res);

    }

    public static ArrayList<String> getStairPaths(int n) {

        ArrayList<String> res = new ArrayList<>();

        if(n == 0){

            res.add("");

            return res;

        }

        if(n<0) return res;

        

        ArrayList<String> path1 = getStairPaths(n-1), path2 = getStairPaths(n-2), path3 = getStairPaths(n-3);

        

        for(String s:path1)

            res.add("1"+s);

        

        for(String s:path2)

            res.add("2"+s);

        

        for(String s:path3)

            res.add("3"+s);

        

        return res;

    }

}