All possible paths for a robot moving along a NxN grid

Problem

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?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

 Solution
 We solved the similar question here, where we had to find the count of number of paths. Here we have to print the paths.

Method 1 - Recursion
Since we know that one can only move either down or right at any point in time

• Base case: f(N, 0) = 1, f(0, N) = 1
• Recursion: f(N, N) = f(N, N-1) + f(N-1, N)

If we want to get number of possible paths :

public static int allPossiblePaths(int M, int N) {
    if (N == 0 || M == 0)
        return 1;
    return allPossiblePaths(M - 1, N) + allPossiblePaths(M, N - 1);
}

But if want to store the paths as well, we have to pass the set to hold the values as well:

public static int AllPossiblePathsWithObstacles(int M, int N,
        Set<Pair<Integer>> obstacles) {
    if (obstacles.contains(new Pair<Integer>(M, N)))
        return 0;
    else {
        if (N == 0 || M == 0)
            return 1;
        return AllPossiblePathsWithObstacles(M - 1, N, obstacles)
                + AllPossiblePathsWithObstacles(M, N - 1, obstacles);
    }
}

Also, we can print the paths as we go.

public static void PrintAllPossiblePathsWithObstacles(int M, int N,
        Set<Pair<Integer>> obstacles, String path) {
    if (obstacles.contains(new Pair<Integer>(M, N)))
        return;
    else {
        if (M == 0) {
            for (int i = 0; i < N; ++i)
                path = "DOWN " + path;
            System.out.println(path);
        } else if (N == 0) {
            for (int i = 0; i < M; ++i)
                path = "RIGHT " + path;
            System.out.println(path);
        } else {
            PrintAllPossiblePathsWithObstacles(M - 1, N, 
                    obstacles, "RIGHT " + path);
            PrintAllPossiblePathsWithObstacles(M, N - 1, 
                    obstacles, "DOWN " + path);
        }
    }
}

References  
tian runhe,
kodeknight,