【蓝桥杯】第七届国赛C语言B组 2.凑平方数（dfs+STL）

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

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

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

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

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

仍然没什么思路   很久没写代码 真的都退化了

代码来源：https://blog.csdn.net/riba2534/article/details/72480145

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[10] = {0,1,2,3,4,5,6,7,8,9};
ll n1[10];
set<string>s;

void dfs(int step,int num)
{
    if(step == 10)   // 用完了10个数
    {
        ll n2[10];
        for(int i = 0;i < num;i++)
        {
             n2[i] = n1[i];
        }
        sort(n2,n2+num);
        string xu;
        char str[100];
        for(int i = 0;i < num;i++)
        {
            sprintf(str,"%lld",n2[i]);   // 转换成字符串
            xu += str;
            xu += "-";
        }
        cout << xu << endl;
        s.insert(xu);   
        return ;
    }
    if(a[step] == 0)
    {
        n1[num] = 0;
        dfs(step+1,num+1);
    }
    else
    {
        ll sum  = 0;
        for(int i = step;i < 10;i++)
        {
            sum = sum*10+a[i];   // 算出当前所得到的值
            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(a,a+10));
    cout << s.size() << endl;
    return 0;
}