Leetcode 351 Android Unlock Patterns

I am trying to solve this problem from Leetcode. 351. Android Unlock Patterns. But I can't find the bug after about 5 hours of debugging. Here's the problem description:

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

Rules for a valid pattern:

Each pattern must connect at least m keys and at most n keys.

All the keys must be distinct.

If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.

The order of keys used matters.

Explanation:
| 1 | 2 | 3 |
| 4 | 5 | 6 | 
| 7 | 8 | 9 | 
Invalid move: 4 - 1 - 3 - 6 Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2 Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6 Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

I use backtracking to solve this problem, and so that I can't use too complex test cases for debugging. My code can pass when n = m =1 and n = m = 2 but failed when n = m = 3. My code will output 304 instead of 320.

I know the lock pattern is symmetric, that is, the dots at the corner and the dots at the middle of the edges will have the same output, so if we found one, we can just multiply by four. Finally, deal with center dots. For m = n = 3, I even tried to draw every possible combination, and I got the corner dot has 31, the middle dot has 35, and the center dot has 40, so the total combination will be 31 * 4 + 35 * 4 + 40 = 304. I check and redraw several times, and still can't find where are the missed 16.

I also checked posts from the discussion section of this problem. I feel the approaches are very similar, but I don't know why mine will fail.

Here is my code

class Solution {
    // Every dot can to go. 
    // 1 2 3
    // 4 5 6
    // 7 8 9
    int[][] directions = new int[][] {
        {0},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8},
        {1, 2, 3, 5, 7, 8, 9},
        {1, 2, 3, 4, 6, 7, 8, 9},
        {1, 2, 3, 5, 7, 8, 9},
        {2, 4, 5, 6, 8},
        {1, 3, 4, 5, 6, 7, 9},
        {2, 4, 5, 6, 8}
    };
    int m, n;

    public int numberOfPatterns(int m, int n) {
        this.m = m;
        this.n = n;
        int res = 0;
        boolean[] visited = new boolean[10];
        res += dfs(1, 1, 0, visited) * 4;
        res += dfs(2, 1, 0, visited) * 4;
        res += dfs(5, 1, 0, visited);

        return res;
    }

    public int dfs(int cur, int len, int tempRes, boolean[] visited) {
        if (len > n || visited[cur]) return tempRes;
        if (len >= m && len <= n) tempRes++;
        visited[cur] = true;
        for (Integer child: directions[cur]) {
            tempRes = dfs(child, len + 1, tempRes, visited);
        }
        visited[cur] = false;
        return tempRes;
    }
}

All help will be great, thank you very much.

Solution

Valid move: 6 - 5 - 4 - 1 - 9 - 2 Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

Your code has not accounted for this possibility. This explains why patterns of length 3 are slightly under counting by 16: starting from the middle 5, the following patterns are possible:

5->1->9, 5->2->8, 5->3->7 etc (8 patterns in all moving to every adjacent square from the center, then jumping back across the center).

Starting from key 4, there are two patterns being skipped: 4->1->7 and 4->7->1. This is mirrored 3 additional times (we can start at any side point, {2, 4, 6, 8}). 8 + 8 = 16, accounting for all of the missing patterns.

If you adjust your logic to handle this, you should be back on track.