【回溯算法】LCR081.组合总和

LCR 081. 组合总和 解题思路

初始化一个空的列表 res 来存储所有满足条件的组合，以及一个空的列表 track 来跟踪当前正在构建的组合，同时还有一个整数 trackNum 来跟踪当前组合的总和。

定义一个名为 combinationSum 的方法，该方法接受两个参数 candidates 和 target，分别表示候选数数组和目标值。

在 combinationSum 方法内部，首先检查如果候选数数组为空，则直接返回一个空列表，因为无法从空数组中找出满足条件的组合。

调用 backtrack 方法开始生成组合。

在 backtrack 方法中，首先检查当前组合的总和是否等于目标值 target，如果是，则将当前组合添加到 res 中。

如果当前组合的总和已经超过了目标值 target，则直接返回，因为后续选择会使总和更大，无法满足条件。

遍历从 start 开始到数组末尾的所有元素，表示在当前位置做出选择。

将选择的元素添加到 track 中，并更新 trackNum 的值。

递归调用 backtrack 方法，传递相同的候选数数组和目标值，但起始位置更新为 i，表示可以重复选择当前元素。

当递归调用返回后，撤销上一步的选择，即从 track 中移除最后一个元素，并更新 trackNum 的值。

当遍历完成时，所有满足条件的组合都已经生成，最后将 res 返回作为结果。

class Solution { List<List<Integer>> res = new LinkedList<>(); List<Integer> track = new LinkedList<>(); int trackNum = 0; public List<List<Integer>> combinationSum(int[] candidates, int target) { if(candidates.length == 0){ return new LinkedList<>(); } backtrack(candidates,target,0); return res; } void backtrack(int[] candidates,int target,int start){ // 子集满足条件 加入 if(trackNum == target){ res.add(new LinkedList<>(track)); } if(trackNum > target){ return;// 提前结束 } for(int i = start; i < candidates.length;i++){ // 进行选择 track.addLast(candidates[i]); trackNum += candidates[i]; backtrack(candidates,target,i);// 表示可以重复选择 trackNum -= candidates[i]; track.removeLast(); } } }