351. Android Unlock Patterns (https://leetcode.com/problems/android-unlock-patterns/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…

351. Android Unlock Patterns (#1 Backtracking).java

// Backtracking solution
// Time: O(C(9, n)), 4ms
// Space: O(1), 33.1mb
class Solution {
    int ans = 0;
    
    public int numberOfPatterns(int m, int n) {
        // Init the tables to check whether the line from curr to next is valid
        boolean[] used = new boolean[10];
        int[][] skip = new int[10][10];
        skip[1][3] = skip[3][1] = 2;
        skip[1][7] = skip[7][1] = 4;
        skip[3][9] = skip[9][3] = 6;
        skip[7][9] = skip[9][7] = 8;
        skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = 5;
        skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;
        used[0] = true; 
        // !!: Need to be true because we need used[skip[curr][next]] to be true for lines not passing through any num
        
        // Calculate the solutions using symatricity
        numberOfPatternsR(m, n, used, skip, 1, 1);
        numberOfPatternsR(m, n, used, skip, 1, 2);
        ans *= 4;
        
        numberOfPatternsR(m, n, used, skip, 1, 5);
        
        return ans;
    }
    
    private void numberOfPatternsR(int m, int n, boolean[] used, int[][] skip, int index, int curr) {
        // Add the ans if the length is between m and n (including m and n)
        if(index >= m) {
            ans++;
        }
        
        // Base case
        if(index == n) {
            return;
        }
        
        // Select curr
        used[curr] = true;
        
        // Recursion explore
        for(int next = 1; next <= 9; next++) {
            if(used[next] || !used[skip[curr][next]]) {
                // Invalid line from curr to next
                continue;
            }
            
            numberOfPatternsR(m, n, used, skip, index + 1, next);
        }
        
        // Unselect: Backtracking
        used[curr] = false;
    }
}