Problem: 351. 安卓系统手势解锁

方案

回溯，因中间的点只可能是2,4,6,8,5，所以使用变量k2, k4, k6, k8, k5来代表前面的点是否出现了2,4,6,8,5，若没有出现，但是出现了13, 31, 17, 71, 39, 93, 79, 97, 28, 82, 46, 64, 19, 91, 37, 73这样的组合，就说明不需要往下回溯的，只需要continue就行，这样就可以剪枝的。要避免重复，需要用到状态数组status。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

https://leetcode.cn/problems/android-unlock-patterns/solutions/2796546/351-an-zhuo-xi-tong-shou-shi-jie-suo-by-7kndv/

Code

class Solution {
public:
    unordered_set<int> ute;
    bool status[10];
    int count = 0;
    bool k2 = false, k4 = false, k6 = false, k8 = false, k5 = false;
    void recursion(int cnt, int pre, int num) {
        if(num==cnt) {
            count++;
            return;
        }
        for(int i = 1; i <= 9; i++) {
            if(status[i]) continue;
            if(!k2 && ((i==1 && pre==3) || (i==3 && pre==1))) continue;
            else if(!k4 && ((i==1 && pre==7) || (i==7 && pre==1))) continue;
            else if(!k6 && ((i==3 && pre==9) || (i==9 && pre==3))) continue;
            else if(!k8 && ((i==7 && pre==9) || (i==9 && pre==7))) continue;
            else if(!k5 && ((i==2 && pre==8) || (i==8 && pre==2)|| (i==4&&pre==6)||(i==6&&pre==4)||(i==1&&pre==9)||(i==9&&pre==1)||(i==3&&pre==7)||(i==7&&pre==3)) ) continue;
            if(i==2) k2 = true;
            else if(i==4) k4 = true;
            else if(i==6) k6 = true;
            else if(i==8) k8 = true;
            else if(i==5) k5 = true;
            status[i] = true;
            recursion(cnt, i, num + 1);
            status[i] = false;
            if(i==2) k2 = false;
            else if(i==4) k4 = false;
            else if(i==6) k6 = false;
            else if(i==8) k8 = false;
            else if(i==5) k5 = false;
        }
    }
    int numberOfPatterns(int m, int n) {
        memset(status, 0, sizeof(status));
        for(int i = m; i <= n; i++)
            recursion(i, -1, 0);
        return count;
    }
};