好吧，又回来回溯算法了，yes，之前写过两篇自学的回溯算法，然鹅，如今再碰到基本一模一样的题题，还是不会做啊啊啊，好吧，那就从头来过，再次肝几道简单的回溯题。
相关文章点这里：
😅初识回溯算法——（一）组合问题_?????*的博客-CSDN博客
😅 回溯（二）——排列 Leetcode46题_?????*的博客-CSDN博客
目录
1.二叉树中和为某一值的路径，原题链接奉上：
二叉树中和为某一值的路径(二)_牛客题霸_牛客网 (nowcoder.com)
解法：
还是回溯回溯回溯！！！
- 待选集合list先add节点值，然后更新target值
- 判定现有list是否满足条件，如若满足，将待选集合add进总结果集中（这里add的时候注意，一定要是深拷贝，重新new一个赋值过去，new ArrayList<>(list)?；
- 如若不满足，则继续进行回溯操作（故而，判定这里，可根据实际问题进行剪枝操作）
- 回溯操作后，记得回退，继续检测上一步的下一个
import java.util.ArrayList;
import java.util.List;
/**
* 二叉树中和为某一值的路径 初识回溯
*
* @author sunny
* @date 2022/04/05 13:19
**/
public class JZ34_FindPath {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
// res是最终结果集
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
// list是每次回溯时的待选结果集
ArrayList<Integer> list = new ArrayList<>();
Dfs(root, expectNumber, res, list);
return res;
}
private void Dfs(TreeNode root, int expectNumber, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
if (root == null) {
return;
}
// 先添加待选元素
list.add(root.val);
// 更新目标值
expectNumber = expectNumber - root.val;
// 判断是否符合要求
// 如果既走到叶子节点了，目标值又=0了，说明是一条路径，就添加进结果集合res中
if (root.left == null && root.right == null && expectNumber == 0) {
// 注意深浅拷贝，不能写成 res.add(list),因为list只是一个引用，如果不new一个深拷贝，后面的list改变，这里的list也会改变！！！
res.add(new ArrayList<>(list));
}
// 回溯
Dfs(root.left, expectNumber, res, list);
Dfs(root.right, expectNumber, res, list);
// 记得回退
list.remove(list.size() - 1);
}
}2.字符串的排列，原题链接奉上：
字符串的排列_牛客题霸_牛客网 (nowcoder.com)
同力扣47题全排列||
题目：
?思路：
还是回溯！！！
- 先add;
- 再判断是否满足条件以添加进结果集；
- 回溯；
- 回退；
注意点：
- 因为是排列，所以已经排列进待选集合里的就不能再参与，所以引入了boolean变量，标记元素是否已排列进待选集合中
- 如何判断待选集合符合要求呢？💌待选集合个数=字符串长度（所以，在dfs方法中形参还有个count变量，记录集合个数）💌💌待选集合不曾被添加进结果集中，因为有可能字符串中有元素重复，所以我们得到的待选集合也可能重复，所以还要再判断一手是否已经contains了
?
import java.util.ArrayList;
/**
* 字符串的全排列
*
* @author sunny
* @date 2022/04/05 16:13
**/
public class JZ38 {
ArrayList<String> res = new ArrayList<>();
public ArrayList<String> Permutation(String str) {
if (str.length() == 0) {
return res;
}
char[] ch = str.toCharArray();
int n = ch.length;
int count = 0;
// boolean数组标记每个字符是否被使用过
boolean[] isUsed = new boolean[n];
StringBuilder s = new StringBuilder();
Dfs(ch, s, isUsed, count);
return res;
}
private void Dfs(char[] ch, StringBuilder s, boolean[] isUsed, int count) {
// 如果个数够了
if (count == ch.length) {
// 且该种排列尚未添加过，就加入结果集中
if (!isContains(res, s.toString())) {
res.add(new String(s));
}
return;
}
for (int i = 0; i < ch.length; i++) {
// 将还未增加进排列里的add
if (!isUsed[i]) {
s.append(ch[i]);
// 更新count和boolean状态
count += 1;
isUsed[i] = true;
// 回溯
Dfs(ch, s, isUsed, count);
// 回退
s.deleteCharAt(s.length() - 1);
count -= 1;
isUsed[i] = false;
}
}
}
private boolean isContains(ArrayList<String> res, String s) {
return res.contains(s);
}
}也许，勤能补拙叭🥺🥺🥺
?
