凑平方数
把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721
再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等…
注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
注意：需要提交的是一个整数，不要填写多余内容。
答案：300
import java.util.Arrays;
import java.util.HashSet;
public class Main {
public static HashSet<String> set = new HashSet<String>();
public void swap(int[] A, int i, int j) {
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
public void dfsAllSort(int[] A, int step) {
if(step == A.length) {
long[] B = new long[A.length];
dfsSqrtNum(A, 0, B, 0);
return;
} else {
for(int i = step;i < A.length;i++) {
swap(A, i, step);
dfsAllSort(A, step + 1);
swap(A, i, step);
}
}
}
public void dfsSqrtNum(int[] A, int step, long[] B, int num) {
if(step == A.length) {
StringBuffer s = new StringBuffer("");
long[] arrayA = new long[num];
for(int i = 0;i < num;i++)
arrayA[i] = B[i];
Arrays.sort(arrayA);
for(int i = 0;i < num;i++) {
s.append(arrayA[i]);
if(i != num - 1)
s.append("-");
}
set.add(s.toString());
return;
}
if(A[step] == 0) {
B[num] = 0;
dfsSqrtNum(A, step + 1, B, num + 1);
} else {
long sum = 0;
for(int i = step;i < A.length;i++) {
sum = sum * 10 + A[i];
double son = Math.sqrt(sum * 1.0);
long a = (long) son;
if(a == son) {
B[num] = sum;
dfsSqrtNum(A, i + 1, B, num + 1);
}
}
}
}
public static void main(String[] args) {
Main test = new Main();
int[] A = {0,1,2,3,4,5,6,7,8,9};
test.dfsAllSort(A, 0);
System.out.println(set.size());
}
}