43 回溯算法解正方形数组的数目

问题描述：给定一个非负数组A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组，返回A的正方形排列的个数，两个排列A1和A2不同的充要条件是存在某个索引，使得A1[i]1=A2[i]。

回溯算法求解：首先对于数组A进行排序，然后定义一个used数组表征该元素是否被选取，在dfs函数中遍历used数组，如果没有被选取过，则更新used数组，并进入下一个dfs函数中，在退出dfs函数后又进入上一个dfs函数中，进行回溯与还原进行下一次循环。

?void public dfs(int []nums,int [] used,ArrayList<Integer>templist,List<List<Integer>>res)
{
int count=0;
for(String s:templist)
{
count+=s.length();
}
if(count==nums.length)
{
res.add(templist);
return;
}
for(int i=0;i<used.length.i++)
{
if(used[i])
{
continue;
}else
{
if(isSquere(nums[i],templist.get(templist.size()-1))==false)
{
continue;
}
used[i]=true;
templist.add(nums[i]);
dfs(nums,used,templist,res);
used[i]=false;
templist.remove(templist.size()-1);
}
}
}
public Boolean isSquare(int A,int B)
{
int sq=(int)sqrt(A+B);
return SQ*SQ==A+B;
}


public DFS(int []nums)
{
List<List<Integer>>res=new LinkedList<LinkedList<Integer>>();
Boolean []used=new Boolean[];
Array.fill(used,false);
dfs(nums,used,res,new Arraylist<Integer>());
???????return res;
}