LeetCode100之组合总和(39)--Java

1.问题描述

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

示例2

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例3

输入: candidates = [2], target = 1
输出: []

提示

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

难度等级

中等

题目链接

组合总和

2.解题思路

这道题是要我们找到候选数组中加起来等于目标和的所有数，而且候选数组中的数可以重复使用。我们可以定义一个List集合来存储题目要的答案。因为数是可以重复使用的，所以我们的基本思路就是从最小的数开始，不断取出候选数来进行尝试，选上一次已经选过的候选数，也可以选比上一次的候选数还大的数。因此，我们要先对候选数组进行排序，这里排序还有一个好处就是，如果我们已经获取到了目标和，或者加上下一个候选数超过了目标和，后续的候选数都可以不用进行尝试了，因为后面的候选数都比当前的候选数大或者已经找到了。

        //存储结果的List结合
        List<List<Integer>> data = new ArrayList<>();
        //对candidates进行排序，方便后续进行剪枝操作
        Arrays.sort(candidates);

接着，我们用一个递归函数来解决这个问题。

首先，我们要确定一下递归的结束条件，这里我用还需要寻找的目标数总和来判断，如果还需要寻找的目标数为0，说明我们刚好找到了和为target的组合；如果小于0，说明我们本次找的组合超过了target，要舍去，同时也不用往后找了，直接返回就可以了。

        //递归结束条件:找到目标和,将组合存入结果集合中,者还需要寻找的目标和小于0
        if(targetSum == 0){
            data.add(new ArrayList(nums));
            return;
        }
        if(targetSum < 0){
            return;
        }

接着，我们要确定递归的参数。这里我们需要传入候选数组，还需要寻找的目标和，当前已经尝试到的目标数组的数据的索引index，存储最终答案的list集合，存储临时组合的List。

    public void backtrack(int[] candidates,int targetSum,int index,List<List<Integer>> data,List<Integer> nums)

然后，我们就可以来实现递归逻辑了。我们从当前数据的索引开始遍历候选数组，这里我们可以做一个剪枝操作，如果取出的数已经大于还需寻找的目标和，则后续的候选数都可以不用尝试了，一定会大于，因为我们一开始就对数组进行排序了。接着，将当前取出的数放入到临时组合中，调用递归方法寻找以当前组合为子组合的所有组合，这里需要注意的是，我们传入的候选数组数据索引，是最后一个被添加进去的数据的索引，这样我们就可以实现重复选择当前数本身，又不会重复使用比当前数小的数据，导致出现排序不同但是每一个数出现次数相同的组合(不符合题意的)。找到以当前组合为子组合的所有组合之后，要将临时组合中的当前数去掉(回溯)，避免影响其他候选数的组合寻找。

        //遍历candidates数组，进行组合
        for(int i = index;i < candidates.length && targetSum - candidates[i] >= 0;i++){
            //添加到当前组合中
            nums.add(candidates[i]);
            //递归获取以当前组合为子组合的所有组合
            backtrack(candidates,targetSum-candidates[i],i,data,nums);
            //删除当前的候选数,避免影响后面的组合
            nums.removeLast();
        }

最后，将存储结果的集合直接返回即可。

3.代码展示

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //存储结果的List结合
        List<List<Integer>> data = new ArrayList<>();
        //对candidates进行排序，方便后续进行剪枝操作
        Arrays.sort(candidates);
        //调用递归函数
        backtrack(candidates,target,0,data,new ArrayList<>());
        //返回结果
        return data;
    }
    public void backtrack(int[] candidates,int targetSum,int index,List<List<Integer>> data,List<Integer> nums){
        //递归结束条件:找到目标和,将组合存入结果集合中,者还需要寻找的目标和小于0
        if(targetSum == 0){
            data.add(new ArrayList(nums));
            return;
        }
        if(targetSum < 0){
            return;
        }
        //遍历candidates数组，进行组合
        for(int i = index;i < candidates.length && targetSum - candidates[i] >= 0;i++){
            //添加到当前组合中
            nums.add(candidates[i]);
            //递归获取以当前组合为子组合的所有组合
            backtrack(candidates,targetSum-candidates[i],i,data,nums);
            //删除当前的候选数,避免影响后面的组合
            nums.removeLast();
        }
    }
}