Listing all paths through a matrix, stepping right or down only I have the following method, which finds all the possible paths from the top left to bottom right of an N x M matrix. I was wondering what is the best way to optimize it for speed as it is a little slow right now. The resulting paths are then stored in a set.You can only move down or right to an adjacent spot, no diagonals from your current position.

    static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet&lt;String&gt; palindrome) {
        String newString = tempString + arr[i][j];
        if (i == m -1 &amp;&amp; j == n-1) {
            palindrome.add(newString);
            return;
        }
        //right
        if (j+1 &lt; n) {
            printPaths (newString, i, j+1, m, n, arr, palindrome);
        }
        //down
        if (i+1 &lt; m) {
            printPaths (newString, i+1, j, m, n, arr, palindrome);          
        }
    }
static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet&lt;String&gt; palindrome) {


You say palindrome? Maybe you shouldn't recycle names from other tasks.

This method should not be public. And should not be called "printWhatever" as it - fortunately - does not print.

arr is an array, nice, but then why did you write "matrix" in your text? Maybe, because of matrix being a more descriptive name? So use it.

The arguments m and n are redundant as they can be obtained from the matrix (and it's improbably more time-consuming than passing them around). Too many arguments make a method hard to use and to read.

So the public method could be

static public Set&lt;String&gt; allPaths(char [][] matrix) {
    Set&lt;String&gt; result = new HashSet&lt;&gt;();
    addAllPathsTo(result, matrix, "", 0, 0);
    return result;
}


with a helper like

static private void addPathsTo(Set&lt;String&gt; result, String tempString, int i, int j, char [][] matrix) {
    String newString = tempString + arr[i][j];
    int m = matrix.length;
    int n = matrix[0].length;
    if (i == m-1 &amp;&amp; j == n-1) {
        result.add(newString);
        return;
    }
    //right
    if (j+1 &lt; n) {
        addPathsTo(result, newString, i, j+1, matrix);
    }
    //down
    if (i+1 &lt; m) {
        addPathsTo(result, newString, i+1, j, matrix);
    }
}


The optimization by JS1 makes a lot of sense and could be included. My point was clean up only.