39.组合总和

- 日理万妓 2023-10-16 13:22 58阅读 0赞

#### 39.组合总和 ####

*  题干描述
 *  解题思路
 *  回溯三部曲
 *   *  1. 递归函数参数
     *  2. 递归终止条件
     *  3. 单层搜索的逻辑
 *  减枝优化
 *  总结
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

*  所有数字（包括 target）都是正整数。
 *  解集不能包含重复的组合。

示例1：

*  输入：candidates = \[2,3,6,7\], target = 7,
 *  所求解集为： \[ \[7\], \[2,2,3\] \]

示例 2：

*  输入：candidates = \[2,3,5\], target = 8,
 *  所求解集为： \[ \[2,2,2,2\], \[2,3,3\], \[3,5\] \]

## 解题思路 ##

题目中的**无限制重复被选取，吓得我赶紧想想 出现0** 可咋办，然后看到下面提示：1 <= candidates\[i\] <= 200，我就放心了。

本题和**77.组合**，**216.组合总和III** 的区别是：本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。

本题搜索的过程抽象成树形结构如下：  
![在这里插入图片描述][ba49aca6197642df9ab72dd5d1376d7e.png]  
注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

而在**77.组合**和**216.组合总和III**中都可以知道要递归K层，因为要取k个元素的组合。

## 回溯三部曲 ##

### 1. 递归函数参数 ###

这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）

首先是题目中给出的参数，集合candidates, 和目标值target。

此外我还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，我依然用了sum。

**本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？**

我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：**77.组合** ，**216.组合总和III** 。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合。

注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路。

### 2. 递归终止条件 ###

在如下树形结构中：  
![在这里插入图片描述][df8b731f0dbc4532899c94e982c2174c.png]  
从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。

sum等于target的时候，需要收集结果，代码如下：

if(sum > target){
        
    	return;
    }
    if(sum == target){
        
    	result.push_back(path);
    	return;
    }

### 3. 单层搜索的逻辑 ###

单层for循环依然是从startIndex开始，搜索candidates集合。

注意本题和77.组合、216.组合总和III的一个区别是：**本题元素为可重复选取的**。

如何重复选取呢，看代码，注释部分：

for(int i = startIndex; i < candidates.size(); i++){
        
    	sum += candidates[i];
    	path.push_back(candidates[i]);
    	backtracking(candidates, target, sum, i); // 关键点: 不用i+1了，表示可以重复读取当前的数
    	sum -= candidates[i]; // 回溯
    	path.pop_back(); // 回溯
    }

## 减枝优化 ##

在这个树形结构中：  
![在这里插入图片描述][0c7912da0ef64d348173be90216aacad.png]  
以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates\[i\]）已经大于target，就可以结束本轮for循环的遍历。  
![在这里插入图片描述][c480437266b94638b605242fb6d30a31.png]  
for循环减枝代码如下：

for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

## 总结 ##

本题和我们之前讲过的**77.组合** 、**216.组合总和III** 有两点不同：

*  组合没有数量要求
 *  元素可无限重复选取

针对这两个问题，我都做了详细的分析。

并且给出了对于组合问题，什么时候用startIndex，什么时候不用，并用**17.电话号码的字母组合**做了对比。

最后还给出了本题的剪枝优化，这个优化如果是初学者的话并不容易想到。

在求和问题中，排序之后加**剪枝**是常见的套路！

## 代码实现 ##

class Solution {
        
        // 39.组合总和 - 剪枝优化
        public List<List<Integer>> combinationSum(int[] candidates, int target){
        
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(candidates); // 先进行排序
            backtracking2(res, new ArrayList<>(), candidates, target, 0, 0);
            return res;
        }
    
        public void backtracking2(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx){
        
            // 找到了数字和为target的组合
            if(sum == target){
        
                res.add(new ArrayList<>(path));
                return;
            }
    
            for(int i = idx; i < candidates.length; i++){
        
                // 如果 sum + candidates[i] > target就终止遍历
                if(sum + candidates[i] > target) break;
                path.add(candidates[i]);
                backtracking2(res, path, candidates, target, sum + candidates[i], i);
                path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
            }
        }
    }

**参考资料**：[代码随想录-39. 组合总和][-39.]

[Link 1]: https://leetcode.cn/problems/combination-sum/
[ba49aca6197642df9ab72dd5d1376d7e.png]: https://img-blog.csdnimg.cn/ba49aca6197642df9ab72dd5d1376d7e.png
[df8b731f0dbc4532899c94e982c2174c.png]: https://img-blog.csdnimg.cn/df8b731f0dbc4532899c94e982c2174c.png
[0c7912da0ef64d348173be90216aacad.png]: https://img-blog.csdnimg.cn/0c7912da0ef64d348173be90216aacad.png
[c480437266b94638b605242fb6d30a31.png]: https://img-blog.csdnimg.cn/c480437266b94638b605242fb6d30a31.png
[-39.]: https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE