351. Android Unlock Patterns

Practice Android Unlock Patterns for free on NudgeCode: Medium, Backtracking pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

An Android lock screen has 9 dots in a 3 x 3 grid, numbered

1 2 3
4 5 6
7 8 9

An unlock pattern is a sequence of distinct dots. Moving from one dot to the next draws a straight segment; if that segment passes through the center of another dot, that dot must already be in the pattern. For example 1 -> 3 needs 2 first, 1 -> 9 needs 5 first, but 2 -> 9 or 1 -> 6 pass through no dot center and are always allowed.

Return how many distinct patterns use at least m and at most n dots.

Example

m = 1, n = 1  ->  9
m = 1, n = 2  ->  65

Constraints