题目描述

凑平方数

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

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

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

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

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

解题思想

/*
首先要明白的一个问题，就是0--9十个数，如何判断一种满足题意的情况，组合完成？
我的想法就是用一个index来跟踪当前枚举的是第几位。
这道题肯定要用dfs，因此递归结束的条件就可以写成index==10
直接说dfs(i,j)表示枚举的一种满足题意的十位数中的第i位，枚举到第j的平方，所代表的数
比如1,25,6390784这种情况
当枚举到j=1，的时候，满足条件，此时i=1，
然后当枚举到j=5，此时为25，i=3，。。
就是这样。
但是这要解决个问题，首先j的平方，要满足自身没有重复的数字，并且跟前面没有重复的数字。
因此问题就差不多解决了。
我这里写的是dfs(i,j,k)
其中k，表示的含义是枚举到第几列，用于输出。
*/

代码

import java.util.Scanner;
public class Main{
    static int[] vis = new int[10];//全程标记数组
    static int[] temVis =new int[10];//用于检测自身是否有重复
    static long[] res = new long[10];//存满足条件的一组组合，用作输出
    static int ant  = 0; //次数
    public static void main(String[] args){
        //i从第一位开始枚举，j从第几个数开始平方枚举，k当前这种情况的第几块数
        dfs(0,0,0);
        System.out.println(ant);
    }

    public static void dfs(int coun,long last, int resindex){
        if(coun == 10){
        //试探到第十个数，自然完成一组组合
            for(int i=0; i<resindex; ++i)
                System.out.print(res[i]+" ");
            System.out.println("-->"+(ant++));
            return;
        }
        for(long i=last; i<=100000; ++i){
            if(isNorepeat((long)i*i)){//如果自身没有重复的数字
            //并且与当前组合的前面数没有重复，说明当前的i*i可以成为组合的一部分
                mark(i*i); //更新全局标记数组

                int len = String.valueOf((long)i*i).length();//i*i长度
                coun += len; //coun表示当前组合的第几个数 
                res[resindex] = i*i; //用于输出，存满足条件的组合数据

                dfs(coun, i+1, resindex+1);

                remark((long)i*i);//返回上一层
                //这里说一下，为什么要返回上一层，
                //首先代码能执行到这里，有俩种情况
                //其一，递归结束条件有return
                //其二，循环终止
                //显然应该是递归终止，所以说明找到了一种情况，所以需要将当前标记消 
                //去，即返回上一层 
                coun -= len; //长度自然要减下去
            }
        }
    }
    //若此j的平方满足条件，则可以加入待组合的后面
    public static void mark(long num){
        if(num ==0){
            vis[0] = 1;
            return;
        }
        while(num != 0){
            vis[(int) (num%10)] = 1;
            num /= 10;
        }
    }
    //判断当前的数自身是否有重复的数字
    public static boolean isNorepeat(long num){
        for(int i=0; i<10; ++i)
            temVis[i] = 0;
        if(num == 0){
            if(vis[0] == 0){
              vis[0] = 1;
             return true;
            }else
                return false;
        }
        while(num != 0){
            if(temVis[(int) (num%10)]==1 || vis[(int) (num%10)]==1 ){
                return false;
            }
            temVis[(int) (num%10)] = 1;
            num /= 10;
        }
        return true;

    }
    //dfs后，返回上一层
    public static void remark(long num){
        if(num == 0){
            vis[0] = 0;
            return;
        }
        while(num != 0){
            vis[(int) (num%10)] = 0;
            num /= 10;
        }
    }
}