LeetCode-39. 组合总和

￡神魔★判官ぃ 2024-03-26 11:42 52阅读 0赞

#### 目录 ####

*   *  题目思路
     *  回溯

题目来源  
[39. 组合总和][39.]

### 题目思路 ###

搜索的过程抽象成树形结构如下：  
![在这里插入图片描述][577a4089b4a74037a625eefbfc718c23.png]

注意图中叶子节点的返回条件，因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！

### 回溯 ###

*  1.递归函数参数

这里依然是定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）  
首先是题目中给出的参数，集合candidates, 和目标值target。  
此外我还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，我依然用了sum。  
**对于组合问题，什么时候需要startIndex呢？**  
如果是一个集合来求组合的话，就需要startIndex  
多个集合取组合，各个集合之间相互不影响，那么就不用startIndex  
代码如下：

List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        backTracking(int[] candidates, int target,int sum,int startIndex)

*  2.递归终止条件

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

从叶子节点可以清晰看到，终止只有两种情况，sum大于target和sum等于target。  
sum等于target的时候，需要收集结果，代码如下：

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

*  3.单层搜索的逻辑

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

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

完整代码

class Solution {
        
    
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            if(candidates == null){
        
                return result;
            }
            backTracking(candidates,target,0,0);
            return result;
        }
    
        public void backTracking(int[] candidates, int target,int sum,int startIndex){
        
            if(sum > target){
        
                return;
            }
            if(target == sum){
        
                result.add(new ArrayList<>(path));
                return;
            }
            for(int i = startIndex;i<candidates.length;i++){
        
                path.add(candidates[i]);
                sum += candidates[i];
                backTracking(candidates,target,sum,i);  // 关键点:不用i+1了，表示可以重复读取当前的数
                sum -= candidates[i];   // 回溯
                path.remove(path.size()-1);   // 回溯
            }
        }
    
    }

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

[39.]: https://leetcode.cn/problems/combination-sum/
[577a4089b4a74037a625eefbfc718c23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fbffd1c9796e4926a4c0f110fc942372.png
[f22d258964bc48a6b6b5a25d0cba19a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/91ad3d59557342ccb016dfe82f752727.png
[b5e21efc4e8747a5ae71f62c64c333fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0920ef773c1949c9a4501bda15c1b34e.png