你说这题难不难，这题不难。做多了PAT 甲级，DFS,BFS简直不要太熟练。
题目：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
直接上代码，速度击败了97%的人
class Solution {
static int len;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res=new ArrayList<List<Integer>>();//最终的结果
len=candidates.length;
if(len<=0)return new ArrayList<List<Integer>>();
List<Integer> curres=new ArrayList<Integer>();//当前的结果
DFS(0,0,curres,candidates,target,res);
return res;
}
//index：记录当前访问到哪个元素了，cursum：当前的累加和 curres：当前的解
public void DFS(int index,int cursum,List<Integer> curres,int[] candidates,int target,List<List<Integer>> res){
if(cursum>target || index>=len)return;
if(cursum==target){
res.add(new ArrayList<Integer>(curres));
return;
}else{
curres.add(candidates[index]);
DFS(index,cursum+candidates[index],curres,candidates,target,res);
curres.remove(curres.size()-1);
DFS(index+1,cursum,curres,candidates,target,res);
}
}
}
但是我一开始， res.add(new ArrayList<Integer>(curres)); 写的是 res.add(curres); 结果每次返回的都是[ [] [] ]
也就是两个空列表，我真的是不知道为啥。
翻了翻java核心技术卷，才明白其实因为我add的是res，res指向的堆空间的值是在不断变化的（因为我回溯，不断地add和remove），可以把中间的过程打印出来看一下
image.png
这下就一目了然了，虽然我看了核心卷，但是其实自己写程序的时候还是蒙圈了。难受
