代码随想录day23 | leetcode 39.组合总和 40.组合总和II 131.分割回文串

39.组合总和

Java

class Solution {     List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates,target,0,0);return result;}public void backtracking(int[] candidates,int target,int sum,int startIndex){if (sum>target){return;}if (sum == target){result.add(new LinkedList<>(path));return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {path.add(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];path.removeLast();}}
}

回溯方法：backtracking

public void backtracking(int[] candidates, int target, int sum, int startIndex) {if (sum > target) { // 剪枝：如果当前和已经超过目标，直接返回return;}if (sum == target) { // 找到满足条件的组合result.add(new LinkedList<>(path)); // 保存当前路径到结果return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {path.add(candidates[i]); // 做选择：将当前数字加入路径sum += candidates[i]; // 更新路径总和backtracking(candidates, target, sum, i); // 递归，允许重复选择当前数字sum -= candidates[i]; // 撤销选择：恢复之前的状态path.removeLast(); // 从路径中移除最后一个数字，回溯}
}

逻辑解释

1. 递归终止条件
   • sum > target：当前路径总和超过目标值，停止递归。
   • sum == target：找到一组符合条件的组合，将 path 复制加入结果。
2. 循环递归
   • 循环起点：从 startIndex 开始，保证每次递归处理当前数字及其后续数字。
   • 条件：sum + candidates[i] <= target- 剪枝条件，提前终止无意义的递归。
   • 允许重复选择：- 递归调用时仍从 i 开始 (backtracking(candidates, target, sum, i))，因此当前数字可以重复加入组合。
3. 回溯过程
   • path.add(candidates[i]) 和 path.removeLast()：分别表示“选择当前数字”和“撤销选择”。
   • sum += candidates[i] 和 sum -= candidates[i]：动态更新当前路径的总和。

40.组合总和II

树层去重一个数完整搜完一边,另一个重复的数不用搜第二遍

Java

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);boolean[] used = new boolean[candidates.length];Arrays.fill(used,false);backtracking(candidates,target,0,0,used);return result;}public void backtracking(int[] candidates, int target,int sum,int stateIndex,boolean[] used){if (sum>target){return;}if (sum == target){result.add(new ArrayList<>(path));}for (int i = stateIndex; i < candidates.length; i++) {if (i>0&&candidates[i-1]==candidates[i]&&used[i-1]==false){//重要，按层去重continue;}path.add(candidates[i]);sum += candidates[i];used[i] = true;backtracking(candidates,target,sum,i+1,used);path.removeLast();sum -= candidates[i];used[i] = false;}}
}

关键点

1. 数组排序：

	Arrays.sort(candidates);

对数组 candidates 进行排序是为了方便去重和剪枝。排序后，相同的元素会相邻，可以通过简单的逻辑避免重复。

2. 去重逻辑：

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

这一部分用于按“层”去重。如果当前元素与前一个元素相同，且前一个元素在当前层没有被使用（used[i - 1] == false），就跳过这个元素，避免重复组合。

3. 递归与回溯：
   • 递归条件：递归深入到下一层（选择下一个数字）。
   • 回溯操作：撤销上一步的选择（移除当前路径中的数字，恢复 sum 和 used 的状态）。

---

代码逻辑

全局变量

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

• result：存储最终的所有满足条件的组合。
• path：存储当前递归路径上的数字组合。

---

主函数

public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 排序，方便去重和剪枝boolean[] used = new boolean[candidates.length]; // 记录每个数字是否使用backtracking(candidates, target, 0, 0, used); // 初始状态return result;
}

• 对数组排序后，初始化 used 数组为 false。
• 调用回溯函数 backtracking 开始寻找组合。

---

回溯函数

public void backtracking(int[] candidates, int target, int sum, int stateIndex, boolean[] used) {if (sum > target) {return; // 剪枝：当前组合和大于目标值}if (sum == target) {result.add(new ArrayList<>(path)); // 找到符合条件的组合，加入结果集return;}for (int i = stateIndex; i < candidates.length; i++) {if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {continue; // 去重：跳过相同的元素}path.add(candidates[i]); // 添加当前数字到路径sum += candidates[i]; // 更新路径和used[i] = true; // 标记当前数字为已使用backtracking(candidates, target, sum, i + 1, used); // 递归到下一层path.removeLast(); // 回溯，撤销选择sum -= candidates[i]; // 恢复路径和used[i] = false; // 恢复使用状态}
}

---

重点逻辑

1. 递归结束条件：
   • 当 sum > target 时，直接返回，表示当前路径无效。
   • 当 sum == target 时，说明找到一个符合条件的组合，将其加入 result。
2. 去重：

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

按“层”去重。只有当前层的数字和前一个数字相同时，才需要检查是否跳过。
3. 递归与回溯：
- 递归：将当前数字加入路径后，继续递归处理下一层。
- 回溯：撤销选择，包括移除路径中的数字，恢复 sum 和 used 的状态。

131.分割回文串

Java

class Solution {List<List<String>> result = new ArrayList<>();LinkedList<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s,0);return result;}public void backtracking(String s,int startIndex){if (startIndex >= s.length()){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s,startIndex,i)){String a = s.substring(startIndex,i+1);path.add(a);}else {continue;}backtracking(s,i+1);path.removeLast();}}boolean isPalindrome(String s,int start,int end){for (int i = start,j = end; i <j ; i++,j--) {if (s.charAt(i)!=s.charAt(j)){return false;}}return true;}
}

全局变量

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

• result：存储所有满足条件的分割方案。
• path：当前递归路径，表示当前的分割方案。

---

主函数

public List<List<String>> partition(String s) {backtracking(s, 0); // 从索引 0 开始划分字符串return result;
}

• 调用回溯函数 backtracking 从字符串的第一个字符开始分割。
• 返回所有满足条件的方案。

---

回溯函数

public void backtracking(String s, int startIndex) {if (startIndex >= s.length()) {result.add(new ArrayList<>(path)); // 如果遍历到字符串末尾，记录当前路径return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s, startIndex, i)) { // 判断从 startIndex 到 i 的子串是否是回文String a = s.substring(startIndex, i + 1); // 取出当前回文子串path.add(a); // 加入路径} else {continue; // 如果不是回文，跳过本次循环}backtracking(s, i + 1); // 递归处理剩下的部分path.removeLast(); // 回溯，移除最后一个子串}
}

• 终止条件：- 当 startIndex 超过或等于字符串长度时，说明已经分割完毕，记录当前路径。
• 递归逻辑：- 从 startIndex 开始，尝试分割到每个可能的位置 i。
  • 如果 s[startIndex...i] 是回文，则加入路径，并递归处理 s[i+1...end]。
  • 递归返回后，回溯移除当前子串。

---

判断是否为回文

boolean isPalindrome(String s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false; // 如果两端字符不相等，不是回文}}return true; // 如果所有字符都相等，是回文
}

• 双指针法，检查从 start 到 end 的子串是否为回文。
• 左右两端字符逐步比较，如果有任意一对不相等，则不是回文。

---

算法流程

1. 从字符串 s 的第一个字符开始，尝试划分每个可能的回文子串。
2. 如果找到一个回文子串，加入当前路径，并继续递归处理剩余部分。
3. 当划分到字符串末尾时，将当前路径记录为一种有效方案。
4. 回溯时移除最后一个子串，尝试其他划分方式。