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 Count ways to reach the n'th stair - GeeksforGeeks
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);
}
}
}
great explanation.
Happy to help!!