1.这一题也是回溯的问题,使用了递归的方式来实现回溯。
ps:leetcode上的题目尽量不要定义全局变量,不然就会向我今天一样。
运行的时候是正确的,但是提交的时候就错误了。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list=new ArrayList<List<Integer>>();
backTracking(list,candidates,target,new ArrayList<Integer>(),0,0);
return list;
}
public void backTracking(List<List<Integer>> list,int[] candidates,int target,ArrayList<Integer> b,int sum,int count){
if(sum==target){
list.add(b);
}else if(sum<target){
for(int i=count;i<candidates.length;i++){
ArrayList<Integer> c=new ArrayList<Integer>(b);
c.add(candidates[i]);
backTracking(list,candidates,target,c,sum+candidates[i],i);
}
}
}
}