Boardpath(Count , Print)

Take as input N, a number. N is the size of a snakes and ladder board (without any snakes and ladders). Take as input M, a number. M is the number of faces of the dice.

a. Write a recursive function which returns the count of different ways the board can be traveled using the dice. Print the value returned.

b. Write a recursive function which prints dice-values for all valid paths across the board (void is the return type for function).

Input Format

Enter a number N (size of the board) and number M(number of the faces of a dice)

Constraints

None

Output Format

Display the number of paths and print all the paths in a space separated manner

Sample Input

3
3

Sample Output

111 12 21 3 4

import java.util.Scanner;

public class BoardPath {
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int m=s.nextInt();
printPaths(0,n,m,"");
System.out.print("\n"+noOfWays(0,n,m));
s.close();

}
private static int noOfWays(int current,int destination,int maxStep)
{
if(current==destination)
{
return 1;
}
if(current>destination)
{
return 0;
}
int ans=0;
for(int steps=1; steps<=maxStep && current+steps<=destination; steps++)
{
ans+=noOfWays(current+steps,destination,maxStep);
}
return ans;

}
private static void printPaths(int current,int destination,int maxStep,String ans)
{
if(current==destination)
{
System.out.print(ans+" ");
return;
}
if(current>destination)
{
return;
}
for(int steps=1; steps<=maxStep && current+steps<=destination; steps++)
{
printPaths(current+steps,destination,maxStep,ans+steps);
}

}

}