Leetcode - 40. 组合总和 II

class Solution {

    // 本题和上一题类似，只不过数组中可能有重复元素，且同一个元素只能使用一次
    // 只需注意去重的要点即可：1. 排序； 2. 从左到右的顺序； 3. 避免连续使用相同的数字
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        
        // 对数组进行排序，方便去重
        Arrays.sort(candidates);
 
        // used数组用于存储被选中的数字，由于一个数字只能使用一次，因此used的长度和candidates相同即可
        int[] used = new int[candidates.length];

        // usedLen代表used数组的实际长度
        int usedLen = 0;
 
        // 回溯法
        find(candidates, 0, used, usedLen, target, ret);
        
        return ret;
    }
 
    // 该方法的功能是从candidates[start]到candidates[candidates.length - 1]范围内找出若干个数，使其和等于target
    // candidate用于告知本方法有哪些数字可用
    // used和usedLen用于告知本方法之前的步骤中已经添加了哪些数字
    // start表示要从candidates的哪个下标开始遍历，保证只能接着往下遍历，防止最终结果出现重复元素
    // target用于告知本方法要使用这些可用的数字凑成什么样的和
    public void find(int[] candidates, int start, int[] used, int usedLen, int target, List<List<Integer>> ret){
        
        // 如果target是0，说明当前used数组中的有效数字之和正好是题目要的target，因此把这些数字保存下来
        if(target == 0){
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < usedLen; i++) {
                list.add(used[i]);
            }
            ret.add(list);
            return;
        }
 
        // 记录上次循环中使用的值，防止连续使用相同的数字
        int lastUsedValue = -1;
 
        // 否则从start下标开始遍历数组
        for (int i = start; i < candidates.length; i++) {
 
            // 如果当前值已经大于target，由于数组是升序的，因此肯定找不到和为target的组合，因此直接结束循环
            if (candidates[i] > target) {
                break;
            }
            
            // 如果当前值与之前被使用的值相同，则跳过该值
            if (candidates[i] == lastUsedValue) {
                continue;
            }
            
            // 否则，选中当前值，并继续调用find()方法（同时更新lastUsedValue值）
            // 注意，被调用的find()是从i + 1开始遍历数组，因为同一个元素只能使用一次
            lastUsedValue = used[usedLen] = candidates[i];
            find(candidates, i + 1, used, usedLen + 1, target - candidates[i], ret);
        }
    }
}