## Thursday, 30 January 2014

### Print all possible paths from top left to bottom right of a mXn matrix

#### Question :

The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.(GeeksForGeeks)

#### Idea :

The algorithm is a simple recursive algorithm, from each cell first print all paths by going down and then print all paths by going right. Do this recursively for each cell encountered.

#### Solution :

```/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 30/1/14
* Time: 4:39 PM
* To change this template use File | Settings | File Templates.
*/
public class AllPathsPrinter {

int [][] array;
int rowCount;
int colCount;

public AllPathsPrinter(int [][]array){

this.array = array;
rowCount = array.length;
colCount = array[0].length;

}

public void printAllPaths(int currX, int currY, String path){

if(currX == rowCount-1){
for(int j=currY;j<=colCount-1;j++){
path = path + array[currX][j];
}
System.out.println("Path : " + path);
return;
}

if(currY == colCount-1){
for(int i=currX;i<=rowCount-1;i++){
path = path + array[i][currY];
}
System.out.println("Path : " + path);
return;
}
path = path + array[currX][currY];
printAllPaths(currX+1, currY, path);
printAllPaths(currX, currY+1, path);

}

public static void main(String args[]){

int [][] ar = new int[][]{{1, 2, 3}, {4, 5, 6}};
AllPathsPrinter allPathsPrinter = new AllPathsPrinter(ar);
allPathsPrinter.printAllPaths(0,0,"");

}

}
```

Path : 1456
Path : 1256
Path : 1236