回溯算法04-组合总数(Java)

4.组合总数

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思路分析

本题的组合总数相较于之前的组合总数III，本次可以选取同一个数字，此时只需要将startIndex的取法进行修改，之前如果每个数只可以放一次，那么startIndex就需要不断的递增，这样才可以避免重复，但是如果可以重复取数，那么startIndex则不需要进行递增，只需要与i保持相同，即每次从索引为i开始取数就可以了。

整体思路分析

1.首先定义一个空的链表 path 用来保存当前的组合，定义一个空的二维列表 result 用来保存所有符合条件的组合。

2.在 backtrace 方法中，首先判断当前的和是否等于目标值 target，如果是，则将当前的组合加入到结果列表中，并返回。如果当前的和大于目标值 target，则直接返回。

3.遍历候选数组 candidate，从 startIndex 开始遍历，依次选择数字。将选择的数字添加到当前的组合 path 中，更新当前的和 sum。
调用递归函数 backtrace，传入新的 startIndex，目标值 target，和 sum。

4.递归结束后，将之前添加的数字从组合 path 中移除，更新当前的和 sum。

5.回溯到上一层，继续选择下一个数字进行递归。

举例说明

Java代码实现

LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrace(candidates, 0, target, 0);
        return result;
    }

    private void backtrace(int[] candidate, int startIndex,int target, int sum) {
        if (target == sum) {
            result.add(new ArrayList<>(path));
            return;
        } else if (sum > target){
            return;
        }

        for (int i = startIndex; i < candidate.length; i++) {
            path.add(candidate[i]);
            sum += candidate[i];
            backtrace(candidate, i, target, sum);
            sum -= candidate[i];
            path.removeLast();
        }
    }