把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721
再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…
注意，0可以作为独立的数字，但不能作为多位数字的开始。 分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
注意：需要提交的是一个整数，不要填写多余内容。
#include<iostream> #include<algorithm> #include<cstring> #include<stdio.h> using namespace std; typedef long long LL; #define maxn (100005*2) long long table[maxn],cnt=0; int t=0; /* 国赛的回溯题目， 没有注意到的地方就是对于x为0的处理， 在用while结构中，如果x为0，则过程直接被跳过了。。。 */ bool check(long long x) { int bo[10]; memset(bo,0,sizeof(bo)); while(x) { if(bo[x]) return false; bo[x]=1; x/=10; } return true; } void inittable(int N) { for(long long i=0;i<N;i++) { if(!check(i*i)) continue; table[cnt++]=i*i; } } int ans[10],result=0; bool judge(long long x) { while(x) { if(ans[x]) return false; x/=10; } return true; } bool judge() { for(int i=0;i<10;i++) if(!ans[i]) return false; return true; } void make(long long x) { if(x==0) ans[0]=1; while(x) { ans[x]=1; x/=10; } } void muns(long long x) { if(x==0) ans[0]=0; while(x) { ans[x]=0; x/=10; } } void dfs(int n) { if(judge()) { result++; return ; } if(n>=cnt) return ; for(int i=n;i<cnt;i++) { if(!judge(table[i])) continue; make(table[i]); dfs(i+1); muns(table[i]); } } int main() { inittable(100000); memset(ans,0,sizeof(ans)); dfs(0); cout<<result<<endl; return 0; }