把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721
再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等...
注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
其实一开始i想到了要用next_permutation和dfs，但是具体的思路想不通。
看了学长的代码才会做。记录一下。
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[20]={
0,1,2,3,4,5,6,7,8,9};
set<string> st;
bool judge(ll x){
if(!x) return 1;
ll tmp = (ll)sqrt(x);
return tmp*tmp == x;
}
void dfs(int pos, vector<ll> v){
if(pos == 10){
sort(v.begin(),v.end());
string ans="";
for(int i=0; i<v.size(); i++){
char t[32];
sprintf(t, "%lld", v[i]);
ans = ans +" "+t;
}
//cout<<ans<<endl;
st.insert(ans);
return;
}
ll tmp=0;
if(a[pos]==0){
v.push_back(0);
dfs(pos+1,v);
}else{
for(int i=pos; i<=9; i++){
tmp = tmp*10+a[i];
if(judge(tmp)){
v.push_back(tmp);
dfs(i+1, v);
v.pop_back();
}
}
}
}
int main(){
do{
vector<ll> v;
v.clear();
dfs(0, v);
}while(next_permutation(a, a+10));
printf("%d\n", st.size());
return 0;
}
