LCR 082. 组合总和 II

解题思路

• 定义了一个 Solution 类。
• 使用了 LinkedList 来存储结果集 res，以及用于回溯过程中追踪当前组合的 track 列表和追踪当前组合的和的 trackNum 变量。
• combinationSum2 方法是入口方法，用于求解给定 candidates 数组中元素的组合，使其和等于目标值 target。
• 在方法中，首先对 candidates 数组进行排序，以便处理重复元素。
• 调用 backTrack 方法进行回溯搜索。
• backTrack 方法是核心递归函数，用于生成所有可能的组合。它采用深度优先搜索的策略。
• 在 backTrack 方法中，首先判断当前 trackNum 是否等于目标值 target，如果等于则将当前组合加入结果集 res。
• 然后判断当前 trackNum 是否大于目标值 target，如果大于则返回，进行剪枝操作。
• 接着进入循环遍历 candidates 数组，从 start 索引位置开始。
• 在循环中，首先进行剪枝操作，防止重复元素被选取。
• 然后将当前元素加入组合 track，并更新 trackNum。
• 递归调用 backTrack 方法，更新 start 索引为 i+1，继续搜索下一层。
• 递归完成后，撤销选择，将当前元素从组合 track 中移除，并更新 trackNum。
• 最终返回结果集 res。

class Solution {List<List<Integer>> res = new LinkedList<>();List<Integer> track = new LinkedList<>();int trackNum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {if(candidates.length == 0){return new LinkedList<>();}Arrays.sort(candidates);//排序 将相同的元素安排在一起backTrack(candidates,target,0);return res;}void backTrack(int[] candidates,int target,int start){if(trackNum == target){res.add(new LinkedList<>(track));return;}if(trackNum > target){return;}for(int i = start; i < candidates.length; i++){// 剪枝 防止重复元素if(i > start && candidates[i] == candidates[i - 1]){continue;}// 做出选择track.add(candidates[i]);trackNum += candidates[i];// 递归遍历下一层回溯backTrack(candidates,target,i + 1);// 撤销选择track.removeLast();trackNum -= candidates[i];}}
}