Algorithm for finding all paths in a NxN grid

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);
    }
}

Leave a Comment