一、题目内容
二、题目分析
这道题目的示例[2,3,6,7],可以用下图方式遍历的理解。
如图,首先有四种选择方法,可以在2,3,6,7中任选一个,然后将它加到临时列表中去,之后每层都有四种选择方法(因为可重复选择),每次选择后我们用sum+=选择的值,当我们一直选择到sum等于target的时候,说明我们找到了一种情况满足条件,那我们就将这一临时列表加到结果列表里去,如果sum>target,则说明当前的值不应该选择,直接return即可。只有当sum<target时,才可以进行下去,遍历整数数组,然后加入当前数值,回溯,撤销。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list =new ArrayList<> ();
Arrays.sort(candidates);
backtrack(list,new ArrayList<>(),candidates,target,0);
return list;
}
public void backtrack(List<List<Integer>> list,List<Integer> templist,int []candidates,int target,int index)
{
if(sum(templist)==target)
{
list.add(new ArrayList<>(templist));
return;
}
if(sum(templist)>target)
return;
for(int i=index;i<candidates.length;i++)
{
templist.add(candidates[i]);
backtrack(list,templist,candidates,target,i);
templist.remove(templist.size()-1);
}
}
public int sum(List<Integer> l)
{
int s=0;
for(int i=0;i<l.size();i++)
{
s+=l.get(i);
}
return s;
}
}