Pascal Walk(DFS Java)

import java.util.*;
public class Solution {
    static ArrayList<Location> res;
    static class Location {
        public int i;
        public int j;
        public Location(int i1, int j1) {
            i = i1;
            j = j1;
        }
        public String toString() {
            return this.i + " " + this.j;
        }
    }
    public static void main(String[] args) {
        int[][] table = new int[32][1000000];

        table[1][1] = 1;
        for(int i = 2; i <= 31; i++) {
            for(int j = 1; j < 1000000; j++) {
                table[i][j] = table[i-1][j-1] + table[i-1][j];
            }
        }


        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            res = new ArrayList<>();
            boolean[][] visited = new boolean[32][1000000];
            ArrayList<Location> currentPath = new ArrayList<>();
            currentPath.add(new Location(1, 1));
            dfs(table, visited, 1, 1, currentPath, 1, n);
            System.out.println("Case " + "#" + (i + 1) + ": ");
            for(Location x: res) {
                System.out.println(x);
            }
        }

    }
    static void dfs(int[][] table, boolean[][] visited, int i, int j, ArrayList<Location> currentPath, int currentSum, int totalSum) {


        if(visited[i][j] || currentPath.size() > 500)
            return;

        visited[i][j] = true;
        if(currentSum == totalSum) {
            res = new ArrayList<Location>(currentPath);
            return;
        }

        int p1 = table[i][j - 1];
        int p2 = table[i][j + 1];
        int p3 = table[i - 1][j];
        int p4 = table[i - 1][j - 1];
         int p5 = 0, p6 = 0;
        if(i + 1 <= 31) {
            p5 = table[i + 1][j];
            p6 = table[i + 1][j + 1];
        }

        if(p1 != 0 && currentSum + p1 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i, j - 1));
            dfs(table, visited, i, j - 1, modifiedPath, currentSum + p1, totalSum);
        }

        if(p2 != 0 && currentSum + p2 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i, j + 1));
            dfs(table, visited, i, j + 1, modifiedPath, currentSum + p2, totalSum);
        }

        if(p3 != 0 && currentSum + p3 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i - 1, j));
            dfs(table, visited, i - 1, j, modifiedPath, currentSum + p3, totalSum);
        }

        if(p4 != 0 && currentSum + p4 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i - 1, j - 1));
            dfs(table, visited, i - 1, j - 1, modifiedPath, currentSum + p4, totalSum);
        }

        if(i + 1 <= 31 && p5 != 0 && currentSum + p5 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i + 1, j));
            dfs(table, visited, i + 1, j, modifiedPath, currentSum + p5, totalSum);
        }

        if(i + 1 <= 31 && p6 != 0 && currentSum + p6 <= totalSum) {
            ArrayList<Location> modifiedPath = new ArrayList<Location>(currentPath);
            modifiedPath.add(new Location(i + 1, j + 1));
            dfs(table, visited, i + 1, j + 1, modifiedPath, currentSum + p6, totalSum);
        }

    }
}