LeetCode第40题组合总和II

继续打卡算法题，今天学习的是LeetCode第40题组合总和II，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

这个题目和39题组合总和有相似的地方，不同的地方在于本题要求一个数字在一个组合里只能使用一次，并且不包含重复的组合，这样我们每次拼凑组合的时候不能包含自己当前元素。

以23367组合成11为例子，还是通过树形结构来说明组合生成的过程，每个数字选择完成之后，从下一个数字开始选择生成组合，从下图可以看出，同一层的数字如果出现了重复，后面的这个数字其实是需要丢弃掉的，因为他生成组合的过程和前面生成组合过程会重叠。

本题解题秘诀

1、同一层的相同数字，需要去重。

2、需要使用一个数组来标记哪些数字已经使用过了。

编码解决

class Solution {

    private List<List<Integer>> result = new ArrayList<>();


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        //先排序，为了去重复
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtracking(candidates,target, new ArrayList<>(), 0, 0, used);
        return result;
    }


    public void backtracking(int[] candidates, int target,List<Integer> path, int startIndex, int sum, boolean[] used) {

        //结束条件
        if(sum == target) {
            result.add(new ArrayList(path));
            return;
        }
        if(sum > target) {
            return;
        }
        //递归单层逻辑
        for(int i=startIndex; i<candidates.length; i++) {
               //同一层，两个相同的数字，需要去重，use[i-1]==false 这个很关键啊
               if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false) {
                   continue;
               }
               path.add(candidates[i]);
               sum += candidates[i];
               //同一个组合里使用了，标记一下
               used[i] = true;
               //开始递归 startIndex传i,就是考虑每个数字都可以重复使用的情况
               backtracking(candidates, target, path, i+1, sum, used);
               //回溯
               sum = sum - candidates[i];
               used[i] = false;
               path.remove(path.size()-1);
        }
    }
}

总结

本题是组合的变体题目，增加了一些额外的要求，我们需要灵活应变，它本质上还是回溯+递归，只不过增加了减枝操作。