Optimizing an algorithm java

Question

Hi I have the following method. What it does is it finds all the possible paths from the top left to bottom right of a 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 resulted paths are then stored in a set.

EDIT I forgot to clarify you can only move down or right to an adjacent spot, no diagonals from your current position

For example
ABC
DEF
GHI

A path from the top left to bottom right would be ADEFI

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

EDIT Here is the entirety of the code

public class palpath {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("palpath.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int d = Integer.parseInt(st.nextToken());


        char[][] grid = new char [d][d];

        String index = null;

        for(int i = 0; i < d; i++)
        {
            String temp = br.readLine();
            index = index + temp;
            for(int j = 0; j < d; j++)
            {
                grid[i][j] = temp.charAt(j);
            }
        }

        br.close();

        int counter = 0;

        HashSet<String> set = new HashSet<String>();
        printPaths ("", 0, 0, grid.length, grid[0].length, grid, set);

        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            String temp =  it.next();
            StringBuilder sb = new StringBuilder(temp).reverse();
            if(temp.equals(sb.toString()))  {
                counter++;
            }

        }




        pw.println(counter);
        pw.close();

    }


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

Answer 1

Given a graph of length M x N, all paths from (0,0) to (M-1, N-1) that only involve rightward and downward moves are guaranteed to contain exactly M-1 moves rightward and N-1 moves downward.

This presents us with an interesting property: we can represent a path from (0,0) to (M-1, N-1) as a binary string (0 indicating a rightward move and 1 indicating a downward move).

So, the question becomes: how fast can we print out a list of permutations of that bit string?

Pretty fast.

public static void printPaths(char[][] arr) {
    /* Get Smallest Bitstring (e.g. 0000...111) */
    long current = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        current <<= 1;
        current |= 1;
    }

    /* Get Largest Bitstring (e.g. 111...0000) */
    long last = current;
    for (int i = 0; i < arr[0].length - 1; i++) {
        last <<= 1;
    }

    while (current <= last) {
        /* Print Path */
        int x = 0, y = 0;
        long tmp = current;
        StringBuilder sb = new StringBuilder(arr.length + arr[0].length);
        while (x < arr.length && y < arr[0].length) {
            sb.append(arr[x][y]);
            if ((tmp & 1) == 1) {
                x++;
            } else {
                y++;
            }
            tmp >>= 1;
        }
        System.out.println(sb.toString());

        /* Get Next Permutation */
        tmp = (current | (current - 1)) + 1;
        current = tmp | ((((tmp & -tmp) / (current & -current)) >> 1) - 1);
    }
}