代码随想录算法训练营第二十三天

LeetCode.39 组合总和

题目链接 组合总和

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {if (candidates == null || candidates.length == 0) {return resList;}Arrays.sort(candidates);dfs(candidates, target, 0, 0);return resList;}public void dfs(int[] candidates, int target, int index, int sum) {if (sum > target) {return;}if (sum == target) {resList.add(new ArrayList<>(res));return;}for (int i = index; i < candidates.length; i++) {if (i > index && candidates[i] == candidates[i - 1]) {continue;}res.add(candidates[i]);dfs(candidates, target, i, sum + candidates[i]);res.remove(res.size() - 1);}}
}

解题思路

这段代码实现了组合总和问题的解决方案，允许元素重复使用但会避免重复的组合结果。让我为你分析一下这段代码的工作原理：

1. 整体思路：使用深度优先搜索 (DFS) 结合回溯法，寻找所有可能的组合，使其和等于目标值。

2. 关键变量：

   • resList：存储所有符合条件的组合结果
   • res：用于当前正在构建的组合

3. 核心逻辑：

   • 首先对候选数组进行排序，这是为了方便去重和剪枝
   • 通过 DFS 递归探索所有可能的组合
   • 当当前和等于目标值时，将当前组合加入结果集
   • 当当前和超过目标值时，停止继续递归（剪枝）

LeetCode.40 组合总和II

题目链接 组合总和II

题解

class Solution {List<List<Integer>> resList = new ArrayList<List<Integer>>();List<Integer> res = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {if (candidates == null || candidates.length == 0) {return resList;}Arrays.sort(candidates);dfs(candidates, target, 0, 0);return resList;}public void dfs(int[] candidates, int target, int index, int sum) {if (sum > target) {return;}if (sum == target) {resList.add(new ArrayList<>(res));return;}for (int i = index; i < candidates.length; i++) {if (i > index && candidates[i] == candidates[i - 1]) {continue;}res.add(candidates[i]);dfs(candidates, target, i + 1, sum + candidates[i]);res.remove(res.size() - 1);}}
}

解题思路

这段代码实现了组合总和问题的另一个变种 ——组合总和 II 的解决方案。与上一个版本相比，它有一个关键区别：每个元素只能使用一次。

让我分析一下这段代码的特点：

1. 问题特点：

   • 给定一个候选数组和目标值，找出所有不重复的组合，使组合中元素的和等于目标值
   • 每个元素在每个组合中只能使用一次
   • 结果集中不能有重复的组合

2. 与上一版本的核心区别：
   递归调用时传入的索引是 i + 1 而不是 i：

   dfs(candidates, target, i + 1, sum + candidates[i]);
   

    

   这个改动确保了每个元素在一个组合中只能被使用一次。

3. 去重逻辑：
   同样的去重逻辑与之前相同：

   if (i > index && candidates[i] == candidates[i - 1]) {continue;
   }
   

    

   结合数组已排序的前提，这段代码能有效避免产生重复的组合。例如，对于数组 [1,1,2]，它会确保只考虑第一个 1 开头的组合，跳过第二个 1 开头的组合，从而避免重复。

4. 算法流程：

   • 对数组排序，为去重和剪枝做准备
   • 用 DFS 探索所有可能的组合
   • 当当前和等于目标值时，记录当前组合
   • 当当前和超过目标值时，停止递归（剪枝）
   • 每个元素只能使用一次，且通过排序逻辑确保结果不重复

LeetCode.131 分割回文串

题目链接 分割回文串

题解

class Solution {List<List<String>> resList = new ArrayList<List<String>>();List<String> res = new ArrayList<>();public List<List<String>> partition(String s) {if(s.length() == 0) return resList;dfs(s,0,new StringBuilder());return resList;}public void dfs(String s,int index,StringBuilder sb){if(index == s.length()){resList.add(new ArrayList<>(res));return ;}for(int i = index;i<s.length();i++){sb.append(s.charAt(i));if(check(sb)){res.add(sb.toString());dfs(s,i + 1,new StringBuilder());res.remove(res.size() - 1);}}}private boolean check(StringBuilder sb){for (int i = 0; i < sb.length()/ 2; i++){if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}}return true;}
}

解题思路

这段代码实现了字符串分割回文子串的功能，即找出一个字符串所有可能的分割方案，使得每个子串都是回文串。让我分析一下这段代码的实现思路和潜在问题：

代码分析

1. 核心功能：

   • 将输入字符串s分割成若干个子串，每个子串都是回文串
   • 收集所有可能的分割方案并返回

2. 实现思路：

   • 使用 DFS（深度优先搜索）结合回溯法探索所有可能的分割方式
   • resList存储所有有效的分割方案
   • res存储当前正在构建的分割方案

3. 关键逻辑：

   • 从index位置开始遍历字符串，尝试构建回文子串
   • 使用StringBuilder逐步构建子串并检查是否为回文
   • 若当前子串是回文，则递归处理剩余部分
   • 递归终止条件：当index达到字符串长度时，说明当前前分割方案加入结果集