40. 组合总和 II

题目：https://leetcode-cn.com/problems/combination-sum-ii/

代码：

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //使用冒泡算法对数组排序（从大到小排序）
        int temp;
        for (int i = 0; i < candidates.length-1; i++) {
            for (int j = 0; j < candidates.length-i-1; j++) {
                if (candidates[j] < candidates[j + 1]) {
                    temp = candidates[j];
                    candidates[j] = candidates[j+1];
                    candidates[j+1] = temp;
                }
            }
        }
        return this.handle(candidates, target,0);
    }

    private List<List<Integer>> handle(int[] candidates, int target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = start; i < candidates.length; i++) {
            int c = candidates[i];
            if (i>start && candidates[i-1]==candidates[i]) {
                //避免重复组合
                continue;
            }
            if (c == target) {
                //刚好相等，这个数直接是结果
                List<Integer> list = new ArrayList<>();
                list.add(c);
                res.add(list);
            } else if (c < target) {
                //小于，递归
                List<List<Integer>> lists = this.handle(candidates, target - c, i+1);
                for (List<Integer> list : lists) {
                    list.add(c);
                }
                res.addAll(lists);
            }
        }
        return res;
    }

}

本题是39. 组合总和这题的基础上进行修改得出，主要的变化是candidates数组中的数可以重复，且每个数字只能被使用1次。

我们考虑在39题的基础上进行改造，因为题目要求每个数字只能被使用1次，那么我们直接在handle函数上增加一个start参数，每一次递归调用的时候，都从下一个数开始找，这样就可以实现每个数字只会被使用1次。但是这也带来了1个问题，因为maxCandidate参数的存在，导致某些组合可能会丢失找不出来，而maxCandidate参数的作用是保证在每一次递归找结果的过程中，都只找比他小的数，也就是说，保证我们是从大数开始找。因为list的添加是从尾部添加的，所以得出最终组合结果都是从小到大排列。既然如此，我们何不直接在递归调用之前，先对数组candidates进行从大到小排序，这样既可去掉maxCandidate这个参数。相应的，我们的避免重复组合的判断方式也要进行相应的修改，只要这个数已经出现过查找过1次，就可以跳过。