My solution with Backtracking

• But I don't know how to make the check generic and simple ...

``````public int numberOfPatterns(int m, int n) {
int result = 0;
for (int i = m; i <= n; i++) {
result += count(i);
}

return result;
}

private int count(int i) {
boolean[] candidates = new boolean[9];

return impl(candidates, i, -1);
}

private int impl(boolean[] candidates, int i, int last) {
if (i == 0) {
return 1;
}

int result = 0;
for (int j = 0; j < 9; j++) {
if (!candidates[j]) {
if (last == -1 || check(candidates, last, j)) {
candidates[j] = true;
result += impl(candidates, i - 1, j);
candidates[j] = false;
}
}
}

return result;
}

private boolean check(boolean[] candidates, int i, int j) {
if (i > j) {
return check(candidates, j, i);
}

if (i / 3 == j / 3) {
for (int k = i + 1; k < j; k++) {
if (!candidates[k]) {
return false;
}
}
}

if (i % 3 == j % 3) {
for (int k = i + 3; k < j; k += 3) {
if (!candidates[k]) {
return false;
}
}
}

if (!candidates[4] && (i == 0 && j == 8 || i == 2 && j == 6)) {
return false;
}

return true;
}``````

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