递归+List深拷贝 || 不能包含重复的组合

39. 组合总和
    给定一个无重复元素的数组 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]
]

网友答案：
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listAll=new ArrayList<List<Integer>>();
        List<Integer> list=new ArrayList<Integer>();
        //排序
        Arrays.sort(candidates);
        find(listAll,list,candidates,target,0);
        return listAll;
    }
    public void find(List<List<Integer>> listAll,List<Integer> tmp,int[] candidates, int target,int num){
        //递归的终点
        if(target==0){
            listAll.add(tmp);
            return;
        } 
        if(target<candidates[0]) return;
        for(int i=num;i<candidates.length&&candidates[i]<=target;i++){
            //深拷贝
            List<Integer> list=new ArrayList<>(tmp);
            list.add(candidates[i]);
            //递归运算，将i传递至下一次运算是为了避免结果重复。
            find(listAll,list,candidates,target-candidates[i],i);
        }   
    } 
}

我的答案：
1、不一定需要排序
2、这样做时间略长，因为getRes方法中for循环比网友答案少了一个终止条件
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> listAll = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        getRes(listAll,list,candidates,target,0);
        return listAll;
    }
    public void getRes(List<List<Integer>> listAll, List<Integer> list, int[] nums, int target, int num){
        if(target == 0){
            listAll.add(list);
            return;
        }
        if(target<0) return;
        for(int i = num; i<nums.length; i++){
            List<Integer> temp = new ArrayList<>(list);
            if(target-nums[i]>=0){
                temp.add(nums[i]);
                getRes(listAll,temp,nums,target-nums[i],i);
            }else{
                continue;
            }
        }
    }
}

---

---

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> listAll = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        getRes(listAll,list,candidates,target,0);
        return listAll;
    }
    public void getRes(List<List<Integer>> listAll, List<Integer> list, int[] nums, int target, int num){
        if(target == 0){
            listAll.add(list);
            return;
        }
        for(int i = num; i<nums.length; i++){
            List<Integer> temp = new ArrayList<>(list);
            if(target-nums[i]>=0){
                temp.add(nums[i]);
                //错误：应该改为i+1，而不是num+1
                getRes(listAll,temp,nums,target-nums[i],num+1);
            }else{
                continue;
            }
        }
    }
}

image.png