Algorithm for finding all paths in a NxN grid

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?

I could find solution to this problem on Google, but I am not very clear with the explanations. I am trying to clearly understand the logic on how to solve this and implement in Java. Any help is appreciated.

Update: This is an interview question. For now, I am trying to reach the bottom-right end and print the possible paths.

Solution 1:

public static int computePaths(int n){
    return recursive(n, 1, 1);      
}   

public static int recursive(int n, int i, int j){
    if( i == n || j == n){
        //reach either border, only one path
        return 1;
    }
    return recursive(n, i + 1, j) + recursive(n, i, j + 1);
}

To find all possible paths:
still using a recursive method. A path variable is assigned "" in the beginning, then add each point visited to 'path'. A possible path is formed when reaching the (n,n) point, then add it to the list.

Each path is denoted as a string, such as " (1,1) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4)". All possible paths are stored in a string list.

public static List<String> robotPaths(int n){
    List<String> pathList = new ArrayList<String>();
    getPaths(n, 1,1, "", pathList);
    return pathList;
}
public static void getPaths(int n, int i, int j, String path, List<String> pathList){
    path += String.format(" (%d,%d)", i , j);
    if( i ==n && j == n){ //reach the (n,n) point
        pathList.add(path);
    }else if( i > n || j > n){//wrong way
        return;
    }else {
        getPaths(n, i +1, j , path, pathList);
        getPaths(n, i , j +1, path, pathList);
    }
}

Solution 2:

I see no indications for obstacles in your question so we can assume there are none.

Note that for an n+1 by n+1 grid, a robot needs to take exactly 2n steps in order to reach the lower right corner. Thus, it cannot make any more than 2n moves.

Let's start with a simpler case: [find all paths to the right down corner]

The robot can make exactly choose(n,2n)= (2n)!/(n!*n!) paths: It only needs to choose which of the 2n moves will be right, with the rest being down (there are exactly n of these).
To generate the possible paths: just generate all binary vectors of size 2n with exactly n 1's. The 1's indicate right moves, the 0's, down moves.

Now, let's expand it to all paths:
First choose the length of the path. To do so, iterate over all possibilities: 0 <= i <= 2n, where i is the length of the path. In this path there are max(0,i-n) <= j <= min(i,n) right steps.
To generate all possibilities, implement the following pseudo-code:

for each i in [0,2n]:
  for each j in [max(0,i-n),min(i,n)]:
    print all binary vectors of size i with exactly j bits set to 1

Note 1: printing all binary vectors of size i with j bits set to 1 could be computationally expensive. That is expected since there are an exponential number of solutions.
Note 2: For the case i=2n, you get j in [n,n], as expected (the simpler case described above).

Solution 3:

https://math.stackexchange.com/questions/104032/finding-points-in-a-grid-with-exactly-k-paths-to-them - look here at my solution. Seems that it is exactly what you need (yes, statements are slightly different, but in general case they are just the same).