题目描述：
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。
至少要分成多少个组？
输入格式
第一行是一个正整数 n。
第二行是 n 个不大于10000的正整数。
输出格式
一个正整数，即最少需要的组数。
数据范围
1≤n≤10
输入样例：
6 14 20 33 117 143 175输出样例：
3分析：
1、确定每一个组中能放哪些数字。 a.某个数放到最后一组中 b.新开一组
这种枚举方式中，如果某个数能够放到当前最后一组中，一定比新开一组 的 方案数少。 枚举的每一个组，都是到了不能再放下任何数的时候（即多加一个数就会导致不是互质的存在），才去新开一个组。这种和第二种枚举方式不同，已经确定的组就不会再放任何的数，而第二种枚举方式，每个组都有可能再加数进去，所以不行。
#include <iostream> #include <vector> using namespace std; const int N = 15; int p[N]; int n; vector<int> group[N]; int res = 15; int st[N]; int gcd(int a , int b){ return b ? gcd(b, a %b) : a; } bool check(int g , int i ){ for(int j = 0 ; j < group[g].size() ; j ++) { if( gcd(group[g][j] , p[i]) != 1) return false; } return true; } void dfs(int g , int start , int cnt){ //当前是第g组 , 当前已分配的数字的总数 if( g >= res ) return ; //当枚举的组数已经超过了res，那就没必要继续做下去了 if( cnt == n ) res = g + 1; //由于if语句的存在，如果还能得到cnt == n 的结果那么g一定比当前的res小 bool flag = true;//判断一下 如果能够放到最后一组就不会新开一组 for(int i = start ; i < n ; i ++) //start组合型枚举方式 { if( !st[i] && check(g,i) ) { st[i] = true; group[g].push_back( p[i] ); dfs( g , i+1 , cnt+1); group[g].pop_back(); st[i] = false; flag = false; } } if( flag ) dfs(g+1 , 0 , cnt );//不能放到最后一组中，新开一组 } int main(){ cin >> n; for(int i = 0 ; i < n ; i ++ ) cin >> p[i]; dfs(0 , 0 , 0); cout << res << endl; return 0; }2、确定每一个数能放到哪个组中。 注意点：并不是说某个数，能够放到已经有的组中就一定比新开一组的总方案数少！！！（不一定哦）
#include <iostream> #include <vector> using namespace std; const int N = 15; int number[N]; int n; vector<int> group[N]; int res = 15; int gcd(int a ,int b){ return b? gcd(b,a%b) : a; } void dfs(int u,int gp){ if( u == n ) { res = min(res , gp); return ; } for(int i = 0 ; i < gp ; i ++) { bool flag = true; for(int j = 0 ; j < group[i].size() ; j ++) { if( gcd(number[u] , group[i][j] ) != 1) { flag = false; break; } } if( flag == true ) { group[i].push_back(number[u]); dfs(u+1,gp); group[i].pop_back(); } } group[gp].push_back(number[u]); dfs(u+1,gp+1); group[gp].pop_back(); } int main(){ cin >> n; for(int i = 0 ; i < n ; i ++) cin >> number[i]; dfs(0,0); cout << res << endl; return 0; }