Finding all path to reach to end

Given a staircase that has ‘n’ step, and you climb the staircase by jumping over the steps. You can cover at max of ‘k’ steps in a single jump. List all the possible sequence of jumps you could take to climb the staircase.

input:
n=4, k=2

output:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2

counting total possible number of path http://www.geeksforgeeks.org/count-ways-reach-nth-stair/
but how to print all path ??

See this. What I did is, made an array path that will store the value of k I am covering at any time in the recursive call. Whenever the call returns, automatically the path array is changed. Also, I am calculating the sum of all values I am covering to reach the nth stair, when I get the desired sum i.e. 4 here, I’ll print the path array. The code will explore all possibilities, hence there might be a situation when my sum exceeds the value of n, i’ll not move further in this case and hence will return. It’s more or less like root-to-leaf path traversal in a tree.

int[][] climbingStaircase(int n, int k) {
if (n == 0 && k == 0) {
return new int[1][0];
}
int[] path = new int[1000];
List<List> matrix = new LinkedList<>();
findsteps(n, k, 0, 0, matrix, path);
return transformList(matrix);
}

int[][] transformList(List<List<Integer>> matrix) {
    int[][] res = new int[matrix.size()][];
    int i = 0;
    for (List<Integer> list : matrix) {
        res[i] = new int[list.size()];
        for (int k = 0; k < res[i].length; k++) {
            res[i][k] = list.get(k).intValue();
        }
        i++;
    }
    return res;
}

void findsteps(int n, int k, int sum, int idx, List<List<Integer>> matrix, int[] path) {
    if (sum == n) {
        List<Integer> res = new LinkedList<Integer>();
        for (int i = 0; i < idx; i++) {
            res.add(path[i]);
        }
        matrix.add(res);
        return;
    }
    if (sum > n)
        return;
    if (sum < n) {
        for (int i = 1; i <= k; i++) {
            path[idx] = i;
            findsteps(n, k, sum + i, idx + 1, matrix, path);
        }
    }
}

@damn_me you are awesome. :slight_smile: great explanation.
Thank you so much.

@cereal_killer We are always here for helping others!! :slight_smile: Btw nice username :stuck_out_tongue: Happy to help!!