acwing1118. 分成互质组（dfs搜索顺序 组合）

给定 nn 个正整数，将它们分组，使得每组中任意两个数互质。
至少要分成多少个组？

输入格式

第一行是一个正整数 nn。
第二行是 nn 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1≤n≤101≤n≤10

输入样例：

6 14 20 33 117 143 175

输出样例：

3

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int p[N];
int group[N][N];        //当前组的小标
bool st[N];
int res = N;
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
//检查是否跟当前组互为质数
bool check(int group[], int gc, int t) {
    for (int i = 0; i < gc; ++i) {
        if (gcd(p[group[i]], p[t]) > 1) return false;
    }
    return true;
}
//g表示第几个组, gc表示第几个组内有多少个数, tc表示已经搜到了多少数, start表示下一个搜的位置
void dfs(int g, int gc, int tc, int start) {
    if (g >= res) return;    //剪枝
    if (tc == n) res = g;
    bool flag = true;   //判断是否加入当前组
    for (int i = start; i < n; ++i) {
        if (!st[i] && check(group[g], gc, i)) {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;
            flag = false;
        }
    }
    if (flag) dfs(g + 1, 0, tc, 0);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> p[i];
    dfs(1, 0, 0, 0);
    cout << res << endl;
    return 0;
}