39. 组合总和
题目链接/文章讲解：代码随想录
视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili
class Solution {
// 存储最终结果的列表
List<List<Integer>> result = new ArrayList<>();
// 存储当前路径的链表
LinkedList<Integer> path = new LinkedList<>();
// 当前路径的和
int sum = 0;
// 主函数，用于调用回溯函数并返回结果
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 对候选数组进行排序，以便后续处理
Arrays.sort(candidates);
// 调用回溯函数，从第一个元素开始
backtracing(candidates, target, 0);
// 返回最终结果
return result;
}
// 回溯函数，用于递归地寻找组合
public void backtracing(int[] candidates, int target, int startIndex) {
// 如果当前路径的和大于目标值，直接返回
if (sum > target) {
return;
}
// 如果当前路径的和等于目标值，将当前路径添加到结果中
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
// 从startIndex开始遍历候选数组
for (int i = startIndex; i < candidates.length; i++) {
// 将当前候选值添加到路径和sum中
sum += candidates[i];
// 将当前候选值添加到路径中
path.add(candidates[i]);
// 递归调用回溯函数，继续寻找组合
backtracing(candidates, target, i);
// 递归返回后，从sum中减去当前候选值
sum -= candidates[i];
// 从路径中移除最后一个元素
path.removeLast();
}
}
}
40.组合总和II
题目链接/文章讲解：代码随想录
视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili
class Solution {
// 存储最终结果的列表
List<List<Integer>> result = new ArrayList<>();
// 存储当前路径的链表
LinkedList<Integer> path = new LinkedList<>();
// 当前路径的和
int sum = 0;
// 主函数，用于调用回溯函数并返回结果
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 对候选数组进行排序，以便后续处理
Arrays.sort(candidates);
// 调用回溯函数，从第一个元素开始
backtracing(candidates, target, 0);
// 返回最终结果
return result;
}
// 回溯函数，用于递归地寻找组合
public void backtracing(int[] candidates, int target, int startIndex) {
// 如果当前路径的和大于目标值，直接返回
if (sum > target) {
return;
}
// 如果当前路径的和等于目标值，将当前路径添加到结果中
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
// 从startIndex开始遍历候选数组
for (int i = startIndex; i < candidates.length; i++) {
// 剪枝操作：如果当前候选值与前一个候选值相同，并且前一个候选值还没有被使用过，跳过当前候选值
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
// 将当前候选值添加到路径和sum中
sum += candidates[i];
// 将当前候选值添加到路径中
path.add(candidates[i]);
// 递归调用回溯函数，从下一个元素开始（避免重复使用同一个数字）
backtracing(candidates, target, i + 1);
// 递归返回后，从sum中减去当前候选值
sum -= candidates[i];
// 从路径中移除最后一个元素
path.removeLast();
}
}
}
在解决组合问题时，如 combinationSum2 这类题目，输入的 candidates 数组可能会包含重复的数字。当题目要求返回的组合是唯一的（即不能包含重复的组合），我们需要采取一定的措施来避免生成重复的结果。
当对 candidates 数组进行排序后，相同的数字会相邻排列。这样，在遍历过程中，如果当前考虑的数字与前一个数字相同，并且前一个数字已经在这个位置被考虑过（即在当前路径中已经被选择过），那么就没有必要再考虑当前这个相同的数字了，因为这样做会导致重复的解。
具体来说，剪枝操作 if (i > startIndex && candidates[i] == candidates[i - 1]) 的目的是跳过所有与前一个已检查过的元素相同的元素。这里的关键是 i > startIndex 这个条件，它确保了只有在当前索引 i 不是 startIndex 的时候才进行跳过操作。这是因为在第一次进入循环的时候，我们希望检查 startIndex 位置的所有可能，包括那些重复的数字。但是在那之后，为了避免重复，我们需要跳过所有与 startIndex 位置上数字相同的后续数字。
通过这种方式，我们保证了每种情况下的唯一性，同时减少了不必要的计算，提高了算法效率。
131.分割回文串
class Solution {
// 存储所有有效的回文分割组合
List<List<String>> result = new ArrayList<>();
// 存储当前的回文分割路径
LinkedList<String> path = new LinkedList<>();
// 主方法，接收字符串 s 并开始回溯
public List<List<String>> partition(String s) {
backtracing(s, 0); // 从索引 0 开始进行回溯
return result; // 返回所有有效的分割组合
}
// 回溯方法，负责生成回文分割
public void backtracing(String s, int startIndex) {
// 如果开始索引超过字符串的长度，说明已生成一个有效组合
if (startIndex >= s.length()) {
result.add(new ArrayList<>(path)); // 将当前路径的副本添加到结果中
return; // 返回以结束当前递归
}
// 遍历从 startIndex 到字符串的每个可能结束索引 i
for (int i = startIndex; i < s.length(); i++) {
// 获取子串
String substring = s.substring(startIndex, i + 1);
// 检查该子串是否为回文
if (check(substring)) {
path.add(substring); // 如果是回文，将其加入当前路径
backtracing(s, i + 1); // 递归调用，处理下一个子串的起始索引
path.removeLast(); // 回溯，移除最后一个添加的子串，恢复路径
}
}
}
// 检查一个字符串是否为回文
public boolean check(String s) {
// 对称比较字符串的字符
for (int i = 0; i < s.length() / 2; i++) {
// 如果发现不相等的字符，返回 false
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
// 如果全部字符相同，返回 true，表示是回文
return true;
}
}