凑平方数

凑平方数 把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721 再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等... 注意，0可以作为独立的数字，但不能作为多位数字的开始。 分组时，必须用完所有的数字，不能重复，不能遗漏。 如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？ 注意：需要提交的是一个整数，不要填写多余内容。

分析：全排列来一次，然后再暴力一个个枚举，用set标记一下，为了方便，set是string的集合（每次最后把数弄成string类存入，不过要先排序，防止数字一样但顺序不同，导致string不同，存入有重复元素）

这里枚举的时候每到是平方数的时候就存入，然后再进行下一个数，若又返回，再继续接着上次的位置枚举，就枚举完了

#include<bits/stdc++.h> #include<set> using namespace std; int Num[10] = {0,1,2,3,4,5,6,7,8,9}; long long int n1[10]; long long int n2[10]; set<string>ans; void dfs(int curx,int num) { if (curx == 10){ for(int i = 0; i < num; i++){ n2[i] = n1[i]; } sort(n2,n2+num); //从小到大排序再存入set，防止重复 char ch; string s; for(int i = 0; i < num; i++){ while(n2[i]){ int t = n2[i]; n2[i] /= 10; ch = t+'0'; s += ch; } s += ' '; } ans.insert(s); } if (Num[curx] == 0){ n1[num] = 0; dfs(curx+1,num+1); } else{ long long int sum = 0; for(int i = curx; i < 10; i++){ sum = sum*10+Num[i]; // cout << sum << endl; double son = sqrt(sum); if (son == (int)son){ //判断是否是完全平方数，若是，则存入 n1[num] = sum; dfs(i+1,num+1); } } } } int main() { do{ memset(n1,0,sizeof(n1)); dfs(0,0); }while(next_permutation(Num,Num+10)); cout << ans.size(); return 0; }