Problem statement

https://leetcode.com/problems/android-unlock-patterns/

Solution

Try to build combination and when we add new number, check:

  1. It is not in the combination already.
  2. If we make jump, make sure, that digit in the middle is already in our combination.
  3. If we do not take jump, nothing else to check.

We can precompute list of all jumps and all inverses. Number in the middle is always mean of two numbers in the jump.

Complexity

Time complexity is $O(n!)$, where $n=9$ is number of digits, space complexity is $O(n)$.

Code

class Solution:
    def numberOfPatterns(self, m, n):
        jumps = {1:(3,7,9), 2:(8,), 3:(1,7,9), 4:(6,),6:(4,), 7:(1,3,9), 8:(2,), 9:(1,3,7), 5:()}
        self.ans = 0
        
        def dfs(built):
            if m <= len(built) <= n:
                self.ans += 1
            if len(built) >= n:
                return
            
            for digit in range(1, 10):
                if str(digit) in built: continue
                if len(built) > 0 and digit in jumps[int(built[-1])]:
                    if str((digit + int(built[-1]))//2) in built:
                        dfs(built + str(digit))
                else:
                    dfs(built + str(digit))
                    
        dfs("")
        return self.ans