# Java solution using backtracking with one loop

• A modification of the solution: https://discuss.leetcode.com/topic/58892/java-solution-using-backtracking-with-one-loop/1

We can use backtracking to automatically include all patterns whose length is within [m,n]

``````public class Solution {
public int numberOfPatterns(int m, int n) {
int[][] jump = new int[10][10];
jump[1][3] = jump[3][1] = 2;
jump[1][7] = jump[7][1] = 4;
jump[3][9] = jump[9][3] = 6;
jump[7][9] = jump[9][7] = 8;
jump[1][9] = jump[9][1] = jump[3][7] = jump[7][3] = jump[2][8] = jump[8][2] = jump[4][6] = jump[6][4] = 5;

boolean[] isVisited = new boolean[10];

int total = dfs(1, isVisited, jump, m, n, 0)*4 + dfs(2, isVisited, jump, m, n, 0)*4 + dfs(5, isVisited, jump, m, n, 0);

}

//return the number of valid patterns starting from 'start'
public int dfs(int start, boolean[] isVisited, int[][] jump, int m, int n, int currLength) {
currLength += 1;
if (currLength > n) {
return 0;
}

isVisited[start]  = true;
int sum = 0;
if (currLength <= n && currLength >= m) sum += 1;

for (int i = 1; i <= 9; i++) {
if (!isVisited[i] && (jump[start][i] == 0 || isVisited[jump[start][i]])) {
sum += dfs(i, isVisited, jump, m, n, currLength);
}
}

isVisited[start] = false;
return sum;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.