Leetcode - 39. 组合总和

class Solution {

    // 使用回溯法；本题的难点是如何去除最终结果中重复的元素，或者说，如何防止重复元素添加到最终结果中
    // 要防止重复元素添加到最终结果中，就要避免得到重复的组合

    // 首先，要对数组进行排序；然后，为了防止得到重复的组合，就要：
    // 1. 必须从左到右遍历数组：
    //    - 假设arr = [1, 2, 5], target = 8，那么可以依次选中[1, 2, 5]这3个数，但不可以是[1, 5, 2]这样的顺序
    // 2. 避免连续使用相同的数：
    //    - 比如在[1, 1, 2, 3, 5]中，第二个1所有的查找结果是包含于第一个1所有的查找结果中的
    //    - 因此在得到第一个1的查找结果后，应该跳过第二个1，直接去获取数字2的查找结果
    //    - 对于本题来说，由于原数组不存在重复元素，因此这一点不需要考虑
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        
        // 对数组进行排序，方便去重
        Arrays.sort(candidates);

        // used数组用于存储被选中的数字，由于一个数字可以被多次选取，因此used数组长度定大一点
        int[] used = new int[100];

        // 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;
        }

        // 否则从start下标开始遍历数组
        for (int i = start; i < candidates.length; i++) {

            // 如果当前值已经大于target，由于数组是升序的，因此肯定找不到和为target的组合，因此直接结束循环
            if (candidates[i] > target) {
                break;
            }
            
            // 否则，选中当前值，并继续调用find()方法
            // 注意，被调用的find()还是从i开始遍历数组，因为同一个元素可以使用多次
            used[usedLen] = candidates[i];
            find(candidates, i, used, usedLen + 1, target - candidates[i], ret);
        }
    }
}