题目:给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
输入:candidates = [2,3,6,7], target = 7,
所求解集为:
[[7],[2,2,3]]
代码: //回溯法,每次回到当前根节点
class Solution {
public List<List
var list=new ArrayList<List
var arr=new ArrayList
int sum=0;
Arrays.sort(candidates);
backTrack(list,arr,candidates,target,sum,0);
return list;
}
public static void backTrack(List<List<Integer>> alist,List<Integer> arr,int[] acandidates, int atarget,int sum,int t){ //t记录当前为第几个数,,i要不小于t
if(sum==atarget){
var temp=new ArrayList<Integer>(arr);
if(!alist.contains(temp)){
alist.add(temp);}
}
if(sum<atarget){
for(int i=t;i<acandidates.length;i++){
sum+=acandidates[i];
if(sum<=atarget){
arr.add(acandidates[i]);
backTrack(alist,arr,acandidates,atarget,sum,i);
arr.remove(arr.size()-1) ; } //数字和小于目标数
sum-=acandidates[i];
}
}
}
}