47 回溯算法解火柴频正方形

本文主要是介绍47 回溯算法解火柴频正方形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：还记得《卖火柴的小女孩》吗，现在，你知道小女孩有多少根火彩，请找出一种能使用所有火柴拼成一个正方形的方法，不能折断或CIA，可以把火柴连接起来，并且每根火柴都要用到；输入为小女孩拥有火彩的数目，每根火柴用其长度表示，输出即为判断是否能用所有的火柴拼成正方形；

回溯算法求解：每根火柴都可以放置于正方形的四条边，遍历所有的火柴依次放入四条边中，并在放完所有火柴之后进行判断，并输出结果；

public Boolean tranceBack(int[] nums,int index,int []size,int target)
{
Boolean flag=true;
for(int i=0;i<size.length;i++)
{
if(size[k]!=target)
{
flag=false;
break;
}
}
if(flag){return true;}
for(int i=0;i<size.length;i++)
{
if(target>size[i]+=nums[index])
{
continue;
}
size[i]+=nums[index];
if(tranceBack(nums,index+1,size,target)){return true;}
size[i]-=nums[index];
}
return false;
}
public Boolean TranceBack(int []nums,int k)
{
int total=0;
for(int num:nums)
{
total+=num;
}
if(total%k!=0){return false;}
int []size=new int[k];
Arrays.fill(size,0);
return tranceBack(nums,0,size,total/k);
}

这篇关于47 回溯算法解火柴频正方形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---