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

39.组合总和

Java

1. class Solution {     
2.     List<List<Integer>> result = new ArrayList<>();
3.     LinkedList<Integer> path = new LinkedList<>();
4.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
5.         Arrays.sort(candidates);
6.         backtracking(candidates,target,0,0);
7.         return result;
8.     }
9.     public void backtracking(int[] candidates,int target,int sum,int startIndex){
10.         if (sum>target){
11.             return;
12.         }
13.         if (sum == target){
14.             result.add(new LinkedList<>(path));
15.             return;
16.         }
17.         for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
18.             path.add(candidates[i]);
19.             sum += candidates[i];
20.             backtracking(candidates,target,sum,i);
21.             sum -= candidates[i];
22.             path.removeLast();
23.          
24.         }
25.     }
26. }

复制代码

回溯方法：backtracking

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

复制代码

逻辑表明

• 递归停止条件
  
  
  
  • sum > target：当前路径总和凌驾目的值，制止递归。
    
  • sum == target：找到一组符合条件的组合，将 path 复制参加效果。
    
  
  
• 循环递归
  
  
  
  • 循环出发点：从 startIndex 开始，包管每次递归处置惩罚当前数字及厥后续数字。
    
  • 条件：sum + candidates <= target- 剪枝条件，提前停止偶尔义的递归。
    
  • 允许重复选择：- 递归调用时仍从 i 开始 (backtracking(candidates, target, sum, i))，因此当前数字可以重复参加组合。
    
  
  
• 回溯过程
  
  
  
  • path.add(candidates) 和 path.removeLast()：分别表现“选择当前数字”和“取消选择”。
    
  • sum += candidates 和 sum -= candidates：动态更新当前路径的总和。
    
  
  

40.组合总和II

树层去重一个数完备搜完一边,另一个重复的数不消搜第二遍
Java

1. class Solution {
2.      List<List<Integer>> result = new ArrayList<>();
3.     LinkedList<Integer> path = new LinkedList<>();
4.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
5.         Arrays.sort(candidates);
6.         boolean[] used = new boolean[candidates.length];
7.         Arrays.fill(used,false);
8.         backtracking(candidates,target,0,0,used);
9.         return result;
10.     }
11.     public void backtracking(int[] candidates, int target,int sum,int stateIndex,boolean[] used){
12.         if (sum>target){
13.             return;
14.         }
15.         if (sum == target){
16.             result.add(new ArrayList<>(path));
17.         }
18.         for (int i = stateIndex; i < candidates.length; i++) {
19.             if (i>0&&candidates[i-1]==candidates[i]&&used[i-1]==false){//重要，按层去重
20.                 continue;
21.             }
22.             path.add(candidates[i]);
23.             sum += candidates[i];
24.             used[i] = true;
25.             backtracking(candidates,target,sum,i+1,used);
26.             path.removeLast();
27.             sum -= candidates[i];
28.             used[i] = false;
29.         }
30.     }
31. }

复制代码

关键点

• 数组排序：
  

1.         Arrays.sort(candidates);

复制代码

对数组 candidates 举行排序是为了方便去重和剪枝。排序后，雷同的元素会相邻，可以通过简朴的逻辑克制重复。

• 去重逻辑：
  

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

复制代码

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

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

---

代码逻辑

全局变量

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

复制代码

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

---

主函数

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

复制代码

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

---

回溯函数

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

复制代码

---

重点逻辑

• 递归竣事条件：
  
  
  
  • 当 sum > target 时，直接返回，表现当前路径无效。
    
  • 当 sum == target 时，分析找到一个符合条件的组合，将其参加 result。
    
  
  
• 去重：
  

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

复制代码

按“层”去重。只有当前层的数字和前一个数字雷同时，才须要查抄是否跳过。
3. 递归与回溯：
- 递归：将当前数字参加路径后，继续递归处置惩罚下一层。
- 回溯：取消选择，包罗移除路径中的数字，规复 sum 和 used 的状态。
131.分割回文串

Java

1. class Solution {
2.        List<List<String>> result = new ArrayList<>();
3.     LinkedList<String> path = new LinkedList<>();
4.     public List<List<String>> partition(String s) {
5.          backtracking(s,0);
6.         return result;
7.     }
9.         public void backtracking(String s,int startIndex){
10.         if (startIndex >= s.length()){
11.             result.add(new ArrayList<>(path));
12.             return;
13.         }
15.         for (int i = startIndex; i < s.length(); i++) {
16.             if (isPalindrome(s,startIndex,i)){
17.                 String a = s.substring(startIndex,i+1);
18.                 path.add(a);
19.             }
20.             else {
21.                 continue;
22.             }
23.             backtracking(s,i+1);
24.             path.removeLast();
25.         }
27.     }
29.         boolean isPalindrome(String s,int start,int end){
30.         for (int i = start,j = end; i <j ; i++,j--) {
31.             if (s.charAt(i)!=s.charAt(j)){
32.                 return false;
33.             }
34.         }
35.         return true;
36.     }
37. }

复制代码

全局变量

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

复制代码

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

---

主函数

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

复制代码

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

---

回溯函数

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

复制代码

• 停止条件：- 当 startIndex 凌驾或即是字符串长度时，分析已经分割完毕，纪录当前路径。
  
• 递归逻辑：- 从 startIndex 开始，实验分割到每个大概的位置 i。
  
  
  
  • 如果 s[startIndex...i] 是回文，则参加路径，并递归处置惩罚 s[i+1...end]。
    
  • 递归返回后，回溯移除当前子串。
    
  
  

---

判定是否为回文

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

复制代码

• 双指针法，查抄从 start 到 end 的子串是否为回文。
  
• 左右两头字符徐徐比力，如果有恣意一对不相称，则不是回文。
  

---

算法流程

• 从字符串 s 的第一个字符开始，实验分别每个大概的回文子串。
  
• 如果找到一个回文子串，参加当前路径，并继续递归处置惩罚剩余部分。
  
• 当分别到字符串末端时，将当前路径纪录为一种有效方案。
  
• 回溯时移除末了一个子串，实验其他分别方式。