1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private int count;
public int countArrangement(int n) {
backtrack(1, n, new boolean[n + 1]);
return count;
}
private void backtrack(int pos, int n, boolean[] visited) {
if (pos > n) {
count += 1;
return;
}
for (int i = 1; i <= n; ++i) {
if (!visited[i] && Math.max(i, pos) % Math.min(i, pos) == 0) {
visited[i] = true;
backtrack(pos + 1, n, visited);
visited[i] = false;
}
}
}
}
|
没想到是用backtrack, 直接暴力解.
时间复杂度: O(k) k是valid的permutation的个数.
空间复杂度: O(n) boolean array, 以及递归用的栈.
