LeetCode39和40：组合总和I和II

参考：https://mp.weixin.qq.com/s/O53R9GqwmqBi-2gRoVuvjA

组合总和I

组合总和I

解析：题目的意思就是从给出的数组中通过相加得到目标数，并且数组中的数是不限次数的使用。这道题目我们可以使用回溯剪枝进行解决。我们这里画一张图就比较容易理解。

图解

解释一下：数组为2,3,8，目标的数字为8，我们第一个数字可以选择2,3,5，如果选2那么，目标数字就变成了6，接着我们还可以继续选择2,3,5,如果仍然选择2的话，我们这里就剩下2了。在我们每一次选一个值的时候，应该先判断这个值是否可选，当target的值为4的时候，我们就不能选择5了，所以在代码中我们每次都应该做一次判断。
我们在【2,3,3】后，就不能再选择【3,2,3】了，其实总结一下规律就是说，当我们选完2的全部之后，后面就不能再出现2了。只能出现3,5。而选择5的时候。只能选择5，这样就不会重复。

public class Solution {

    @Test
    public void test() {
        int[] candidates = {2,3,5};
        int target = 8;
        List<List<Integer>> lists = combinationSum(candidates, target);
        System.out.println(lists);
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result,new ArrayList<Integer>(),candidates,target,0);
        return result;
    }

    /**
     * @param result 最后结果
     * @param now 当前的这一组相加的数组，每向下一个深度的时候，把当前节点的数放进这个数组中
     * @param candidates 初始的数组
     * @param target 目标（剪枝的节点值）当节点值为0的时候，就代表当前now的数组符合要求
     * @param start
     */
    public static void backtrack(List<List<Integer>> result, List<Integer> now, int[] candidates,Integer target,int start){
        // 先进来判断target值为多少，是否已经符合要求
        if (target == 0){
            result.add(now);
            return;// 已经为0了。可以结束了
        }
        // 开始下一节点的搜寻
         for (int i = start; i < candidates.length; i++){
            // 先判断当前的target值与可以选的值比较
             if (target < candidates[i]){
                 continue;
             }
             List<Integer> list = new ArrayList<>(now);
             list.add(candidates[i]);// 先把这个数加入到当前的这个集合中
             // 如果比较过了，就代表小于，这个数可以被选择，那么就进行回溯
             backtrack(result,list,candidates,target - candidates[i],i);
         }
    }
}

组合总和II

组合总和II

public class Solution2 {
    
    @Test
    public void Test(){
        int[] candidates = {1,1,9};
        int target = 10;
        System.out.println(combinationSum2(candidates, target));
    }

    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 先去排序,让数字相同的都排在了临近的地方
        Arrays.sort(candidates);
        backtrack(candidates,target,0,new LinkedList<>());
        return result;
    }
    /**
     *我们类比 组数之和 的第一题去思考，和第一题不同的是这个题目的数字不能重复使用，而且结果中也不能产生相同的结果
     * ps:[2,1,3,1] target:5
     * 只能产生[[2,3],[1,1,3]]
     * 思考：在回溯的时候，应该是这样场景,第一次可选[2,1,3,1].
     * 用过2之后，下一次再挑选的数组应该是[1,3,1]
     */
    public void backtrack( int[] candidates, int target, int start, LinkedList<Integer> now){
        // 先判断当前的值是否与target相同
        if (target == 0){
            result.add(new LinkedList<>(now));
            return;
        }
        if (target > 0){
            for (int i = start; i < candidates.length ; i++){
                // 这里的i>start防止数组下标越界,
                if (i > start && candidates[i] == candidates[i -1] ) continue;
                // 把当前的这个数加入到数组中
                now.add(candidates[i]);
                backtrack(candidates,target - candidates[i],i+1,now);
                now.removeLast();
            }
        }
    }
}