LeetCode-216. 组合总和 III

不念不忘少年蓝@ 2024-03-26 06:56 66阅读 0赞

#### 目录 ####

*   *  题目分析
     *  回溯三部曲
     *  剪枝优化

题目来源  
[216. 组合总和 III][216. _ III]

### 题目分析 ###

这个和leetcode77组合类似  
本题k相当于树的深度，9（因为整个集合就是9个数）就是树的宽度。  
例如 k = 2，n = 4的话，就是在集合\[1,2,3,4,5,6,7,8,9\]中求 k（个数） = 2, n（和） = 4的组合。  
选取过程如图：  
![在这里插入图片描述][9c5c82564439420fbf6f4fd5143c9629.png]  
图中，可以看出，只有最后取到集合（1，3）和为4 符合条件。

### 回溯三部曲 ###

*  1.确定递归函数参数

需要一维数组path来存放符合条件的结果，二维数组result来存放结果集。

List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();

接下来还需要如下参数：

*  targetSum（int）目标和，也就是题目中的n。
 *  k（int）就是题目中要求k个数的集合。
 *  sum（int）为已经收集的元素的总和，也就是path里元素的总和。
 *  startIndex（int）为下一层for循环搜索的起始位置。

List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        backTracking(int targetSum,int k,int startIndex,int sum)

其实这里sum这个参数也可以省略，每次targetSum减去选取的元素数值，然后判断如果targetSum为0了，说明收集到符合条件的结果了，我这里为了直观便于理解，还是加一个sum参数。  
还要强调一下，回溯法中递归函数参数很难一次性确定下来，一般先写逻辑，需要啥参数了，填什么参数。

*  2.确定终止条件

什么时候终止呢？  
所以如果path.size() 和 k相等了，就终止。  
如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。

if(path.size() == k){
        
                if(sum == targetSum){
        
                    result.add(new ArrayList<>(path));
                    return;
                }    
            }

*  3.单层搜索过程

![在这里插入图片描述][9c5c82564439420fbf6f4fd5143c9629.png]  
处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。  
代码如下：

for(int i = startIndex;i<=9;i++){
        
                path.add(i);
                sum += i;
                backTracking(targetSum,k,i+1,sum);  // 注意i+1调整startIndex  
                path.remove(path.size()-1);   // 回溯
                sum -= i;  // 回溯
            }

整体代码如下

class Solution {
        
    
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
    
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            backTracking(n, k, 1,0);
            return result;
        }
    
        public void backTracking(int targetSum,int k,int startIndex,int sum){
        
            if(path.size() == k){
        
                if(sum == targetSum){
        
                    result.add(new ArrayList<>(path));
                    return;
                }    
            }
            for(int i = startIndex;i<=9;i++){
        
                path.add(i);
                sum += i;
                backTracking(targetSum,k,i+1,sum);
                path.remove(path.size()-1);
                sum -= i;
            }
        }
    
    
    }

![在这里插入图片描述][e6446c360b0b447896b57075b0068277.png]

### 剪枝优化 ###

这道题目，剪枝操作其实是很容易想到了，想必大家看上面的树形图的时候已经想到了。  
![在这里插入图片描述][f4f2af6a00ba4e7196811715b8473e5a.png]  
已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。  
那么剪枝的地方可以放在递归函数开始的地方，剪枝代码如下：

class Solution {
        
    
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
    
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            backTracking(n, k, 1,0);
            return result;
        }
    
        public void backTracking(int targetSum,int k,int startIndex,int sum){
        
            if (sum > targetSum) {
        
                return;
            }
            if(path.size() == k){
        
                if(sum == targetSum){
        
                    result.add(new ArrayList<>(path));
                    return;
                }    
            }
            for(int i = startIndex;i<= 9 - (k - path.size()) + 1;i++){
        
                path.add(i);
                sum += i;
                backTracking(targetSum,k,i+1,sum);
                path.remove(path.size()-1);
                sum -= i;
            }
        }
    
    }

![在这里插入图片描述][50205dea67184c05bda096a01ff96595.png]

[216. _ III]: https://leetcode.cn/problems/combination-sum-iii/
[9c5c82564439420fbf6f4fd5143c9629.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/cf47dc69b75646bf805258e4d914e95b.png
[e6446c360b0b447896b57075b0068277.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1965a84f8a7940c4bb8e7d050f97d201.png
[f4f2af6a00ba4e7196811715b8473e5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d086e52f4c5746b691a11d2e2d66752f.png
[50205dea67184c05bda096a01ff96595.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6db2da8664f8403599153dfa0683c255.png