39. Combination Sum

Backtracking

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int index, int target) {
        if (index == candidates.length) {
            // 进入此逻辑的都是由不选择时推进索引驱动进入，因为本题数字可以被重复选择，所以选择完最后一个数字后不会推进索引，所以不会命中当前 if 块，会进入下面的 sum 判断收集结果，所以当前判断放在该方法体开头不会错过结果收集
            // 当前判断如果放在 sum 判断逻辑后亦可
            return;
        }
        if (sum > target) {
            // 因为本题 candidates 均为正数，故可以剪枝
            return;
        }
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return; // 此处的 return 保证了不会重复收集结果
        }

        // not choose
        dfs(resultList, numList, sum, candidates, index + 1, target);

        // choose
        numList.add(candidates[index]);
        dfs(resultList, numList, sum + candidates[index], candidates, index, target); // 因为数字可能被重复选择，所以此处没有推进索引
        numList.remove(numList.size() - 1);
    }
}

以上从各个数字进行选与不选的角度来驱动搜索。

Backtracking

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int startIndex, int target) {
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return;
        }
        if (sum > target) {
            // 因为本题 candidates 均为正数，故可以剪枝
            return;
        }

        // 每次从 startIndex 开始搜索是为了防止出现重复的组合，如 candidates = [2, 3, 6, 7], target = 7, 其中 [2, 2, 3] 与 [2, 3, 2] 都能组成 target, 但是实际上他们为同一个组合
        // 即每次搜索时不再使用 startIndex 之前的数字，而可以使用 startIndex 指向的数字，因为单个数字可以重复使用
        for (int i = startIndex; i < candidates.length; i++) {
            numList.add(candidates[i]);
            dfs(resultList, numList, sum + candidates[i], candidates, i, target); // 此处没有推进索引，因为数字可以重复使用
            numList.remove(numList.size() - 1);
        }
    }
}

以上将选择逻辑抽象为多叉树来进行搜索，其中 for 循环在同一层上进行选择，for 循环内部的 dfs 函数调用则为进入树的下一层节点。

Backtracking

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        Arrays.sort(candidates); // 剪枝提速，非必须
        dfs(resultList, numList, 0, candidates, 0, target);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int sum, int[] candidates, int startIndex, int target) {
        if (sum == target) {
            resultList.add(new ArrayList<>(numList));
            return;
        }

        // 每次从 startIndex 开始搜索是为了防止出现重复的组合，如 candidates = [2, 3, 6, 7], target = 7, 其中 [2, 2, 3] 与 [2, 3, 2] 都能组成 target, 但是实际上他们为同一个组合
        // 即每次搜索时不再使用 startIndex 之前的数字，而可以使用 startIndex 指向的数字，因为单个数字可以重复使用
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                // 在数组升序的情况下才可执行此剪枝
                break;
            }
            numList.add(candidates[i]);
            dfs(resultList, numList, sum + candidates[i], candidates, i, target); // 此处没有推进索引，因为数字可以重复使用
            numList.remove(numList.size() - 1);
        }
    }
}

Reference

39. Combination Sum