题目：
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1:
输入: candidates =[2,3,6,7],target =7, 所求解集为: [ [7], [2,2,3] ]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]思路：总的是使用递归回溯的思想，具体参考了网上大神的代码以及leetcode中执行最快的代码。以下对这两种代码进行分析。
代码：
class Solution {
int n; //类变量
int nums[];
List<List<Integer>>result;
//递归查找的方法
public void find(List<Integer>values,int index,int reserve){
if(reserve==0){ //递归结束的标志，找到了一组组合
ArrayList<Integer>item=new ArrayList<Integer>();
item.addAll(values);
result.add(item); //添加到最终的结果中
}
for(int i=index;i<n;i++) //递归寻找组合
{
if(nums[i]<=reserve){
values.add(nums[i]);
find(values,i,reserve-nums[i]); //每次相减
values.remove(values.size()-1); //把已经添加进去的组合删除
}
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//利用sort进行排序
Arrays.sort(candidates);
//先去掉数组中重复的元素
int i,j,k,n;
n=1;
for(i=1;i<candidates.length;i++){
if(candidates[i]!=candidates[i-1]){
candidates[n++]=candidates[i];
}
}
//给类变量赋值
this.nums=candidates;
this.n=n;
this.result=new ArrayList<List<Integer>>();
find(new ArrayList<Integer>(),0,target);
return this.result;
}
}
执行最快的代码：
基本上也是使用递归的思想。使用相加的思想。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
ArrayList<Integer> cur=new ArrayList<>();
int sum=0;
//校验
if(candidates==null || candidates.length==0) {
return res;
}
dfs(res,candidates,sum,cur,target,0);
return res;
}
public void dfs(List<List<Integer>>res,int[] candidates,int sum,ArrayList<Integer>cur,int target,int start){
if(sum==target){
res.add(new ArrayList<>(cur));
return ;
}
for(int i=start;i<candidates.length;i++){
if(sum+candidates[i]<=target){
sum+=candidates[i];
cur.add(candidates[i]);
dfs(res,candidates,sum,cur,target,i);
sum-=candidates[i];
cur.remove(cur.size()-1);
}
}
}