题解 | #游游的排列统计#
游游的排列统计
http://www.nowcoder.com/questionTerminal/4c58fc41f25d4598913ceda30e66bf01
排列型回溯
有限制条件（当前所选数字 + 前一个选择的数字 不等于素数）下枚举选哪个数字即可
import java.util.*;
public class Main {
private static int[] path;
private static boolean[] visited; // visited[i]表示数字i是否被使用过
private static int n;
private static int ans;
private static void dfs(int i) {
if (i == n) {
ans++;
return;
}
for (int j = 1; j <= n; j++) {
if (!visited[j]) {
if (i > 0) {
if (!isPrime(path[i - 1] + j)) {
visited[j] = true;
path[i] = j;
dfs(i + 1);
visited[j] = false;
}
} else {
visited[j] = true;
path[i] = j;
dfs(i + 1);
visited[j] = false;
}
}
}
}
private static boolean isPrime(int num) {
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
path = new int[n];
visited = new boolean[n + 1];
dfs(0);
System.out.println(ans);
}
}
