# Concise Java, DFS + Memoization + Bits (11ms)

• public int numberOfPatterns(int m, int n) {
if (n == 0 || m > n) return 0;

int[] memoiz = new int[262144];

int c = 0;
for (int i = 0; i < 9; i++)
c += count(m, n, i, 1 << i, 1, memoiz);

return c;
}

private int count(int m, int n, int from, int selected, int selectedCount, int[] memoiz) {
if (selectedCount == n) return 1;

int hash = selected + (1 << (from + 9));
if (memoiz[hash] > 0) return memoiz[hash];

// >= m is a valid move too, so include them
int count = selectedCount >= m ? 1 : 0;

for (int to : NEAR[from]) {
if ((selected & (1 << to)) == 0)
count += count(m, n, to, selected | (1 << to), selectedCount + 1, memoiz);
}

for (int to[] : FAR[from]) {
if ((selected & (1 << to[0])) > 0 && (selected & (1 << to[1])) == 0)
count += count(m, n, to[1], selected | (1 << to[1]), selectedCount + 1, memoiz);
}

return memoiz[hash] = count;
}

final int NEAR[][] = {
{1, 4, 3, 5, 7}, // 0
{0, 2, 3, 4, 5, 6, 8}, // 1
{1, 4, 5, 3, 7}, // 2
{0, 1, 4, 7, 6, 2, 8}, // 3
{0, 1, 2, 3, 5, 6, 7, 8}, // 4
{2, 1, 4, 7, 8, 0, 6}, // 5
{3, 4, 7, 1, 5}, // 6
{6, 3, 4, 5, 8, 0, 2}, // 7
{7, 4, 5, 3, 1} // 8
};

final int FAR[][][] = {
{{1, 2}, {4, 8}, {3, 6}}, // 0
{{4, 7}}, // 1
{{1, 0}, {4, 6}, {5, 8}}, // 2
{{4, 5}}, // 3
{}, // 4
{{4, 3}}, // 5
{{3, 0}, {4, 2}, {7, 8}}, // 6
{{4, 1}}, // 7
{{7, 6}, {4, 0}, {5, 2}}, // 8
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.