robotPath.java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static void main(String args[] ) throws Exception {
        
        int[][] input = new int[][]{ 
            {0,1,0,0,0},
            {0,1,0,0,1},
            {0,1,0,1,1},
            {0,0,0,0,0}};
        
        for (int[] coord : findPaths(input)) {
            System.out.print("(");
            System.out.print(coord[0]);
            System.out.print(",");
            System.out.print(coord[1]);
            System.out.print("), ");
        }
    }
    
    
    private static List<int[]> findPaths(int[][] grid) {
        // 1. dfs + back tracking
        List<int[]> path = new ArrayList<>();
        
        // mem[][] filled with false
        boolean[][] mem = new boolean[grid.length][grid[0].length];
        
        // start 0,0
        if(dfs(grid, 0, 0, path, mem))
            return path.subList(1, path.size());
            
        return new ArrayList<>();
    }
    
    private static boolean dfs(int[][] grid, int row, int col, List<int[]> path, boolean[][] mem) {
        
       
        // reach the end
        if (row == grid.length - 1 && col == grid[0].length - 1) {
            path.add(new int[]{row, col});
            return true;
        }
        
        // out of bounds
        if (row < 0 || col < 0 || row > (grid.length - 1) || col > (grid[row].length - 1)) {
            return false;
        }
      
        if (mem[row][col] == true) {
            return false;
        }
       
        if (grid[row][col] == 1) {
            mem[row][col] = true;
            return false;
        }
            
        int[] cur = new int[]{row, col};
        path.add(cur);
        // => [(0,0)]
        if (!dfs(grid, row + 1, col, path, mem) && !dfs(grid, row, col+1, path, mem)) {
            mem[row][col] = true;
            path.remove(cur);
            return false;
        } else {
            return true;
        }
        
    }
}