#Java #回溯
Feeling and experiences：?
给你一个 无重复元素 的整数数组?candidates 和一个目标整数?target?，找出?candidates?中可以使数字和为目标数?target 的 所有?不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。?
对于给定的输入，保证和为?target 的不同组合数少于 150 个。
和之前的组合问题类似，多用到一个sum，算是加强版了。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates); // 先进行排序
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList<>(path));
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
}
}
}给定一个候选人编号的集合?candidates?和一个目标数?target?，找出?candidates?中所有可以使数字和为?target?的组合。
candidates?中的每个数字在每个组合中只能使用?一次?。
注意：解集不能包含重复的组合。
多了一个去重，这也是难点！
以下参考代码随想录的思路来写的：
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
// 加标志数组，用来辅助判断同层节点是否已经遍历
Arrays.fill(used, false);
// 为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList(path));
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
break;
}
// 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
sum += candidates[i];
path.add(candidates[i]);
// 每个节点仅能选择一次，所以从下一位开始
backTracking(candidates, target, i + 1);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}
主要是used数组的使用：
1.标记元素使用状态：
? used?数组是一个布尔数组，与?candidates?数组的大小相同。它用于标记?candidates?数组中的每个元素是否已经在当前递归路径中被使用过。
? 当一个元素被加入到当前路径?path?中时，其对应的?used?状态被设置为?true，表示该元素已被使用。
? 当从路径中移除该元素时（回溯时），其?used?状态被重新设置为?false。
2. 防止同一层级的重复：
? 在?backTracking?方法中，有一个检查用来防止在同一层级中使用重复的元素。这是通过判断当前元素是否与前一个元素相同，并且前一个元素的?used?状态为?false?来实现的。
? 这个检查确保如果在同一层级中前一个相同的元素未被使用过，则当前元素不会被考虑，从而避免了重复的组合。
3. 处理含重复元素的数组：
? 在包含重复元素的数组中，仅通过?candidates?数组的值可能无法准确判断哪些组合是唯一的。used?数组提供了一种机制来确保即使数组中有重复元素，每个元素也只在其所在层级中被使用一次。
?
看到有不同的解法，不用used数组来记录，而是直接if来判断：
class Solution {
LinkedList<Integer> path = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
boolean[] used;
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 为了将重复的数字都放到一起，所以先进行排序
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return ans;
}
private void backTracking(int[] candidates, int target, int startIndex) {
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue; // 跳过重复元素
}
if (sum + candidates[i] > target) {
break;
}
sum += candidates[i];
path.add(candidates[i]);
backTracking(candidates, target, i + 1); // 从下一个元素开始
sum -= candidates[i];
path.removeLast();
}
}
}
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
思路：
我认为就比之前做的回溯问题，多了一个回文串的判断
1. 初始化和递归函数：
? 创建两个列表：ans?用于存储所有可能的回文分割结果，path?用于在递归过程中存储当前的分割路径。
? 定义一个递归函数?dfs，用于遍历字符串并检查可能的回文子串。
2. 递归终止条件：
? 当?startIndex（当前递归开始的位置）等于字符串的长度时，将当前的?path（代表一个完整的分割方案）复制并添加到?ans?中，然后返回。
3. 回文子串的识别和递归处理：
? 从?startIndex?开始，遍历字符串的每个子串。
? 使用?isHuiwen?函数检查从?startIndex?到当前索引?i?的子串是否为回文。
? 如果是回文，则将该子串添加到?path?中，并递归调用?dfs?函数处理剩余的字符串。
? 完成后，进行回溯，移除?path?中最后添加的子串，以探索其他可能的分割方案。
4. 回文判断函数的实现：
? isHuiwen?函数使用双指针技术检查给定的子串是否为回文。
? 双指针分别从子串的开始和结束进行比较，如果字符不同，则返回?false；如果相同，则继续比较，直到两指针相遇或交错。（这个是很容易判断的）
class Solution {
//分为 分割 和 回文 两个 问题
//构建一个 集合存储结果
List<List<String>> ans = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
dfs(s,0);
return ans;
}
public void dfs(String s,int startIndex){
//终止条件：
if(startIndex == s.length()){
ans.add(new ArrayList(path));
return;
}
for(int i = startIndex;i<s.length();i++){
if(isHuiwen(s,startIndex,i)){
path.add(s.substring(startIndex,i+1));
}
else{
continue;
}
dfs(s,i+1);
//回溯：
path.remove(path.size() - 1);
}
}
//判断是否是回文串
public boolean isHuiwen(String s,int start,int end){
//利用双指针来判断该字符串是否为回文
while(start < end){
if(s.charAt(start) != s.charAt(end)){
return false;
}
start++;
end--;
}
return true;
}
}三个关键点：
终止条件；（为什么是startIndex ==? s.length()? )
字符拼接；(为什么用substring？）
判断回文；（这个容易）
? 终止条件是在?dfs?函数中设置的，当?startIndex（当前递归的起始索引）等于字符串?s?的长度时，触发终止条件。
? 这意味着函数已经考虑了字符串?s?中的所有字符，当前的?path?包含了一种完整的分割方式，其中每个分割都是回文。
画堂晨起，
来报雪花坠~
Fighting！