给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
例子：
输入：candidates＝［2，3，6，7］，target＝7
输出：[[2,2,3],[7]]
解释：
2和3可以形成一组候选，2+2+3=7.注意2可以使用多次。
7也是一个候选，7=7
仅有两种组合。
public class Solution{
List<List<Integer>> res = new ArrayList<>(); // 存储结果
List<Integer> path = new ArrayList<>(); // 存储路径
public List<List<Integer>> combination(int[] candidates, int target){
dfs(candidates, 0 , target);
return res;
}
public void dfs(int[] candidates, int u, int target){
if(target<0){
return;
}
if(target==0){
res.add(new ArrayList(path));
return;
}
for(int i=u; i<candidates.length; i++){
if(candidates[i] < target){
path.add(candidates[i]);
dfs(candidates, i, target-candidates[i]); // 因为可以重复使用，所以还是i
path.remove(path.size()-1); // 回溯，恢复现场
}
}
}
}
上面的代码看起来比较简洁，但是在java里一般不提倡定义全局变量，而且这里是局部方法修改全局变量，会让java工程师非常不爽，所以我们还是将其改造成参数的形式。当然代价是代码看起来略显的复杂，其实和上面完全一样。
public class Solution{
public List<List<Integer>> combination(int[] candidates, int target){
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(candidates, 0, path, res);
return res;
}
public void dfs(int[] candidates, int u, int target, List<Integer> path, List<List<Integer>> res){
if(target < 0) return;
if(target == 0) {
res.add(new ArrayList(path));
return;
}
for(int i=u; i<candidates.length; i++){
if(candidates[i] < target){
path.add(candidates[i]);
dfs(candidates, u, target-candidates[i], path, res); // 因为可以重复使用，所以还是i
path.remove(path.size()-1); // 回溯现场
}
}
}
}