第七届蓝桥杯决赛 凑平方数（非原创）

凑平方数

把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721

再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等...

注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。

如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？

注意：需要提交的是一个整数，不要填写多余内容。

#include <stdio.h>
#include <bits/stdc++.h>
#define mod 1000000007
typedef long long ll;
using namespace std;
int s[10]={0,1,2,3,4,5,6,7,8,9};
int ans;
map<ll,int> mp;
void dfs(ll ss,int x){
    if(x==10){
        cout<<ans<<endl;
        ans++;return;
    }
    if(s[x]==0){  //第一个数不能为0 除了单独一个数 
        if(x==0) dfs(0,x+1);
        return;
    } 
    ll sum=0;
    for(int i=x;i<10;i++){
        sum=sum*10+s[i];    //升序排列  所以下一个数比现在的数大 
        if(sum>ss && mp[sum]) dfs(sum,i+1);
    }
}
int main(){ 
    for(ll i=0;i<=500000;i++) mp[i*i]=1;   //map记住平方数 
    do{
        dfs(-1,0);  
    }while(next_permutation(s,s+10));  //全排列 
    cout<<ans;
    return 0;
}