58 回溯算法求组合问题

2023-12-22 15:52:09

问题描述:给定一个无重复元素的数组nums和一个目标数,找出nums中所有可以使数字和为target的组合;

回溯分析:没个数都有选与不选两种情况,所以回溯深度为nums.length,一旦当前target==0,则加入组合中,到达最后都不能使得target==0,则返回。

public void? tranceBack(int []nums,int target,Link<Integer>templist,int index,List<List<Integer>>res)
{
if(target==0){res.add(new Link<Integer>(templist));return;}
if(index==nums.length){return;}
templist.add(nums[index]);
tranceBack(nums,target-nums[index],templist,index+1,res);
templist.remove(templist.size()-1);
tranceBack(nums,target,templist,index+1,res);
}
public?List<List<Integer>>?TranceBack(int []nums,int target)
{
List<List<Integer>>res=new?List<List<Integer>>();
tranceback(nums,target,new Link<Integer>(),0,res);
return res;
}

//可以看成是求组合问题,需要组合的数字从小到大排列,从而考虑重复问题。

public void tranceBack(int []nums,int index,int target,List<Integer>templist,List<List<Integer>>res)
{
if(target==0){res.add(templist);return;}
for(int i=index;i<nums.length;i++)
{
templist.add(nums[i]);
tranceBack(nums,i+1;target+nums[i],templist,res);
templist.remove(templist.size()-1);
}
}
public List<List<Integer>> TranceBack(int []nums,int target)
{
List<List<Integer>>res=new?List<List<Integer>>();
tranceBack(nums,0,target,new List<Integer>(),res);
???????return res;
}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135151458
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。