# Simple and concise Java solution in 69ms

• The general idea is DFS all the possible combinations from 1 to 9 and skip invalid moves along the way.

We can check invalid moves by using a jumping table. e.g. If a move requires a jump and the key that it is crossing is not visited, then the move is invalid. Furthermore, we can utilize symmetry to reduce runtime, in this case it reduced from ~120ms to ~70ms.

I felt clueless when first encountered this problem, and considered there must be lots of edge cases. Turns out, it's pretty straight forward. Hope this solution helps :D

private int[][] jumps;
private boolean[] visited;

public int numberOfPatterns(int m, int n) {
jumps = new int[10][10];
jumps[1][3] = jumps[3][1] = 2;
jumps[4][6] = jumps[6][4] = 5;
jumps[7][9] = jumps[9][7] = 8;
jumps[1][7] = jumps[7][1] = 4;
jumps[2][8] = jumps[8][2] = 5;
jumps[3][9] = jumps[9][3] = 6;
jumps[1][9] = jumps[9][1] = jumps[3][7] = jumps[7][3] = 5;
visited = new boolean[10];
int count = 0;
count += DFS(1, 1, 0, m, n) * 4; // 1, 3, 7, 9 are symmetrical
count += DFS(2, 1, 0, m, n) * 4; // 2, 4, 6, 8 are symmetrical
count += DFS(5, 1, 0, m, n);
return count;
}

private int DFS(int num, int len, int count, int m, int n) {
if (len >= m) count++; // only count if moves are larger than m
len++;
if (len > n) return count;
visited[num] = true;
for (int next = 1; next <= 9; next++) {
int jump = jumps[num][next];
if (!visited[next] && (jump == 0 || visited[jump])) {
count = DFS(next, len, count, m, n);
}
}
visited[num] = false; // backtracking
return count;
}

• This post is deleted!

• This post is deleted!

• good solution! I modified a little.
public class Solution {

int[][] pattern;
boolean[] used;

public int numberOfPatterns(int m, int n) {
if(m<=0||n>9||m>n) return 0;
//if(n==1) return 9;
int sum=0;

pattern = new int[10][10];

for(int i=1;i<5;i++){
pattern[5-i][i+5] = 5;
pattern[5+i][5-i] = 5;
}
for(int i=2;i<9;i=i+6){
pattern[i-1][i+1] = i;
pattern[i+1][i-1] = i;
}
for(int i=4;i<7;i=i+2){
pattern[i-3][i+3] = i;
pattern[i+3][i-3] = i;
}
int count = 1;
used = new boolean[10];
used[0] = true;

sum += dfs(1,count,m,n)*4;
sum += dfs(2,count,m,n)*4;
sum += dfs(5,count,m,n);
return sum;
}
public int dfs(int k,int count,int m, int n){
int sum = 0;
if(count>=m){
sum++;
}
if(count>=n){
return sum;
}

used[k] = true;
count++;

for(int i=1;i<10;i++){

if( !used[i] && used[pattern[k][i]])
sum = sum + dfs(i,count,m,n);

}
used[k] = false;
return sum;

}

}

• Very concise and elegant.

• Can you explain in the DFS
if (len >= m) count++;

why do we need to increase count when len>=m??

Also, in the for loop of DFS, isn't it like:

count+= DFS(````` ) ?
should there be a + ?

• Because only moves larger than m are valid moves. The question requires us only count moves between m and n;

• beautiful solution! I like it

• @david-liu May you explain the idea behind the jump array a little more?

• @david-liu Is a move from 1 to 6 a valid move? Since jumps[1][6] is initialized to 0 it will be during the dfs routine, but I don't understand why it should.

• @leetcodewinner I had the same question. After checking Android lock pad, I find 1-6 could be linked directly.

• Similar but may be a little easier to remember without the optimization:

public class Solution {

private static final int[][] ON_PATH = buildOnPath();

public int numberOfPatterns(int m, int n) {
boolean visited[] = new boolean[10];
visited[0] = true;
return numberOfPatterns(visited, m, n, 0, 0, 0);
}

private int numberOfPatterns(boolean[] visited, int m, int n, int prev, int curr, int length) {
if (length != 0 && (visited[curr] || length > n)) return 0; // path is too long or we already used this key
if (!visited[ON_PATH[prev][curr]]) return 0; // we haven't visited the key that was on the way here

visited[curr] = true;

int result = 0;
for (int i = 1; i < 10; i++)
result += numberOfPatterns(visited, m, n, curr, i, length + 1);

visited[curr] = false; // backtrack

return length >= m ? result + 1 : result; // if current path is valid length then include it in result
}

private static int[][] buildOnPath() {
int onPath[][] = new int[10][10];

onPath[1][3] = onPath[3][1] = 2;
onPath[1][7] = onPath[7][1] = 4;
onPath[3][9] = onPath[9][3] = 6;
onPath[7][9] = onPath[9][7] = 8;

onPath[1][9] = onPath[9][1] =
onPath[2][8] = onPath[8][2] =
onPath[3][7] = onPath[7][3] =
onPath[4][6] = onPath[6][4] = 5;

return onPath;
}
}

• Very clever solution! The top voted answer runs from scratch for each length, but this one just reuses results from shorter paths.

• count+= DFS(````` ) ?
should there be a + ?

Same question. Anybody can explain?

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