Q:

Possible paths of NxN array traversing from (0, 0) to (N, N) in a positive direction only?

We have an NxN array. I have got the solution to finding out the number of possible paths moving from (0,0) to (N,N) in a positive direction only. You can not move diagonally or backwards.
And the solution is:
private void matrixProblem(int N) {
    System.out.println("Total count is : " + String.valueOf(path((N-1), (N-1))));
}

private int path(int x, int y) {

    System.out.println("x = " + x + " " + "y = " + y);
    if (x < 0 || y < 0) {
        return 0;
    }
    if (x == 0 && y == 0) {
        return 1;
    }

    return path(x - 1, y) + path(x, y - 1);
}

But I also want to print all the possible paths. 
Like for 3x3 array one possible path is: 
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) 
There are 6 possible paths for 3x3 array. This is one example. 
Kindly suggest the best possible way for this.

A:

In order to print all the paths, you'll need to pass around your history. This means:

at every point, add the current entry,
call your function recursively,
remove the last entry again.

Alternatively, you could

at every point, make a copy of the history so far,
add the current entry to the copy,
call your function recursively with the copy,

but the former takes less memory and time. This works:
import java.util.ArrayList;

public final class MatrixProblem {

  private final int mx;
  private final int my;

  public MatrixProblem(int N) {
    mx = N;
    my = N;
  }

  public int countAndPrint() {
    return numPathsTracing(0, 0, new ArrayList<>());
  }

  private int numPathsTracing(int x, int y, ArrayList<String> path) {
    if(x > mx || y > my)
      return 0;
    else if(x == mx && y == my) {
      StringBuilder pathString = new StringBuilder();
      for(String previous : path) {
        pathString.append(previous);
        pathString.append(" -> ");
      }
      pathString.append(pathElement(x, y));
      System.out.println(pathString);
      return 1;
    } else {
      path.add(pathElement(x, y));
      int ret = numPathsTracing(x+1, y, path) + numPathsTracing(x, y+1, path);
      path.remove(path.size() - 1);
      return ret;
    }
  }

  private static String pathElement(int x, int y) {
    return "(" + x + ", " + y + ")";
  }
}

Call as:
int nPaths = new MatrixProblem(3).countAndPrint();
System.out.println("Total count is : " + nPaths);

Output:
(0, 0) -> (1, 0) -> (2, 0) -> (3, 0) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)
Total count is : 20

