# 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.

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

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

int[][] climbingStaircase(int n, int k) {
if (n == 0 && k == 0) {
return new int[1][0];
}
int[] path = new int[1000];
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) {
for (int i = 0; i < idx; i++) {
}