小红的数组构造

[题目链接](https://www.nowcoder.com/practice/7a08d1da90ab43daa2e70112781a3bd9)

思路

给定 $n$ 个数，要求用这些数构造一个长度为 $n$ 的数组，使得相邻两个数之和都是素数，问有多少种不同的构造方案。

本质上就是对数组求满足条件的全排列计数，同时需要处理重复元素。

算法：回溯 + 剪枝

先将数组排序，这样相同的数会聚在一起，方便跳过重复。
用回溯法逐个位置选数：

- 维护 used 数组标记哪些元素已被使用。

- 每次选择下一个数时，检查它与前一个数之和是否为素数，不满足则剪枝。

- 去重技巧：在同一层递归中，如果当前候选数与上一个尝试过的候选数相同，则跳过，避免重复计数。

当排列长度等于 $n$ 时，方案数加一。

样例演示

输入 [1, 1, 2]，排序后仍为 [1, 1, 2]：

第一个位置选 1：

- 第二个位置选 1： $1+1=2$ 是素数。第三个位置选 2： $1+2=3$ 是素数。方案 [1,1,2]。

- 第二个位置选 2： $1+2=3$ 是素数。第三个位置选 1： $2+1=3$ 是素数。方案 [1,2,1]。

第一个位置选 2（跳过第二个 1，因为与第一个 1 重复）：

- 第二个位置选 1： $2+1=3$ 是素数。第三个位置选 1： $1+1=2$ 是素数。方案 [2,1,1]。

共 3 种方案，与预期一致。

输入 [2, 2]： $2+2=4$ 不是素数，无合法排列，输出 0。

复杂度分析

时间复杂度：最坏情况 $O(n! \cdot \sqrt{M})$ ，其中 $M$ 是元素最大值的两倍。由于素数判断的剪枝和重复元素跳过，实际远小于此上界。
空间复杂度： $O(n)$ ，递归栈深度和辅助数组。

代码

C++
Java

class Solution {
public:
    bool isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    int ans;

    void dfs(vector<int>& a, vector<bool>& used, vector<int>& path, int n) {
        if ((int)path.size() == n) {
            ans++;
            return;
        }
        int prev = path.empty() ? -1 : path.back();
        int lastUsed = -1;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (a[i] == lastUsed) continue;
            if (prev != -1 && !isPrime(prev + a[i])) continue;
            lastUsed = a[i];
            used[i] = true;
            path.push_back(a[i]);
            dfs(a, used, path, n);
            path.pop_back();
            used[i] = false;
        }
    }

    int getMethods(vector<int>& a) {
        int n = a.size();
        sort(a.begin(), a.end());
        ans = 0;
        vector<bool> used(n, false);
        vector<int> path;
        dfs(a, used, path, n);
        return ans;
    }
};

import java.util.*;

public class Solution {
    private int ans;

    private boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    private void dfs(int[] a, boolean[] used, int[] path, int depth, int n) {
        if (depth == n) {
            ans++;
            return;
        }
        int prev = depth == 0 ? -1 : path[depth - 1];
        int lastUsed = -1;
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            if (a[i] == lastUsed) continue;
            if (prev != -1 && !isPrime(prev + a[i])) continue;
            lastUsed = a[i];
            used[i] = true;
            path[depth] = a[i];
            dfs(a, used, path, depth + 1, n);
            used[i] = false;
        }
    }

    public int getMethods(int[] a) {
        int n = a.length;
        Arrays.sort(a);
        ans = 0;
        boolean[] used = new boolean[n];
        int[] path = new int[n];
        dfs(a, used, path, 0, n);
        return ans;
    }
}