回溯算法
基础入门
给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。
/* 前序遍历：例题一 */
void preOrderTraversal(TreeNode node) {
if (node != null) {
if (node.val == 7) {
// 记录解
res.add(node);
}
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
“尝试”与“回退”
在二叉树中搜索所有值为 7 的节点， 请返回根节点到这些节点的路径 。
/* 前序遍历：例题二 */
void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
// 尝试
path.add(node);
if (node.val == 7) {
// 记录解
res.add(new ArrayList<>(path));
}
preOrderTraversal(node.left);
preOrderTraversal(node.right);
// 回退
path.remove(path.size() - 1);
}
剪枝
在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径， 并要求路径中不包含值为 3 的 节点 。
/* 前序遍历：例题三 */
void preOrderTraversal(TreeNode node) {
// 剪枝
if (node == null || node.val == 3) {
return;
}
// 尝试
path.add(node);
if (node.val == 7) {
// 记录解
res.add(new ArrayList<>(path));
}
preOrderTraversal(node.left);
preOrderTraversal(node.right);
// 回退
path.remove(path.size() - 1);
}
剪枝:遇到值为3的节点则提前返回
完整代码：
/* 判断当前状态是否为解 */
boolean isSolution(List<TreeNode> currentState) {
return !currentState.isEmpty() && currentState.get(currentState.size() - 1).val == 7;
}
/* 记录解 */
void recordSolution(List<TreeNode> currentState, List<List<TreeNode>> results) {
results.add(new ArrayList<>(currentState));
}
/* 判断在当前状态下，该选择是否合法 */
boolean isValid(List<TreeNode> currentState, TreeNode option) {
return option != null && option.val != 3;
}
/* 更新状态 */
void makeChoice(List<TreeNode> currentState, TreeNode option) {
currentState.add(option);
}
/* 恢复状态 */
void undoChoice(List<TreeNode> currentState) {
currentState.remove(currentState.size() - 1);
}
/* 回溯算法：例题三 */
void backtrack(List<TreeNode> currentState, List<TreeNode> availableChoices, List<List<TreeNode>> results) {
// 检查是否为解
if (isSolution(currentState)) {
// 记录解
recordSolution(currentState, results);
}
// 遍历所有选择
for (TreeNode option : availableChoices) {
// 剪枝：检查选择是否合法
if (isValid(currentState, option)) {
// 尝试：做出选择，更新状态
makeChoice(currentState, option);
// 进行下一轮选择
backtrack(currentState, Arrays.asList(option.left, option.right), results);
// 回退：撤销选择，恢复到之前的状态
undoChoice(currentState);
}
}
}
保留 return记录解后返回，不再继续搜索
删除 return记录解后不返回，继续搜索
全排列问题
输入一个整数数组，其中不包含重复元素，返回所有可能的排列。
/* 回溯算法：全排列 I */
void backtrack(List<Integer> currentState, int[] options, boolean[] used, List<List<Integer>> results) {
// 当状态长度等于元素数量时，记录解
if (currentState.size() == options.length) {
results.add(new ArrayList<>(currentState));
return;
}
// 遍历所有选择
for (int i = 0; i < options.length; i++) {
int option = options[i];
// 剪枝：不允许重复选择元素
if (!used[i]) {
// 尝试：做出选择，更新状态
used[i] = true;
currentState.add(option);
// 进行下一轮选择
backtrack(currentState, options, used, results);
// 回退：撤销选择，恢复到之前的状态
used[i] = false;
currentState.remove(currentState.size() - 1);
}
}
}
/* 全排列 I */
List<List<Integer>> permutationsI(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
backtrack(new ArrayList<>(), nums, new boolean[nums.length], results);
return results;
}
输入一个整数数组，数组中可能包含重复元素，返回所有不重复的排列。
/* 回溯算法：全排列 II */
void backtrack(List<Integer> currentState, int[] options, boolean[] used, List<List<Integer>> results) {
// 当状态长度等于元素数量时，记录解
if (currentState.size() == options.length) {
results.add(new ArrayList<>(currentState));
return;
}
// 遍历所有选择
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < options.length; i++) {
int option = options[i];
// 剪枝：不允许重复选择元素 且 不允许重复选择相等元素
if (!used[i] && !seen.contains(option)) {
// 尝试：做出选择，更新状态
seen.add(option); // 记录选择过的元素值
used[i] = true;
currentState.add(option);
// 进行下一轮选择
backtrack(currentState, options, used, results);
// 回退：撤销选择，恢复到之前的状态
used[i] = false;
currentState.remove(currentState.size() - 1);
}
}
}
/* 全排列 II */
List<List<Integer>> permutationsII(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
backtrack(new ArrayList<>(), nums, new boolean[nums.length], results);
return results;
}
子集和问题
给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。给定数组无重复元素，每个元素可以被选取多次。请以列表形式返回这些组合，列表中不应包含重复组合。
/* 回溯算法：子集和 I */
void backtrack(List<Integer> currentSubset, int target, int[] options, int start, List<List<Integer>> results) {
// 子集和等于 target 时，记录解
if (target == 0) {
results.add(new ArrayList<>(currentSubset));
return;
}
// 遍历所有选择
// 剪枝二：从 start 开始遍历，避免生成重复子集
for (int i = start; i < options.length; i++) {
// 剪枝一：若子集和超过 target ，则直接结束循环
// 这是因为数组已排序，后边元素更大，子集和一定超过 target
if (target - options[i] < 0) {
break;
}
// 尝试：做出选择，更新 target 和 start
currentSubset.add(options[i]);
// 进行下一轮选择
backtrack(currentSubset, target - options[i], options, i, results);
// 回退：撤销选择，恢复到之前的状态
currentSubset.remove(currentSubset.size() - 1);
}
}
/* 求解子集和 I */
List<List<Integer>> subsetSumI(int[] nums, int target) {
List<Integer> currentSubset = new ArrayList<>(); // 状态（子集）
Arrays.sort(nums); // 对 nums 进行排序
int start = 0; // 遍历起始点
List<List<Integer>> results = new ArrayList<>(); // 结果列表（子集列表）
backtrack(currentSubset, target, nums, start, results);
return results;
}
给定一个正整数数组 nums 和一个目标正整数 target ，请找出所有可能的组合，使得组合中的元素和等于 target 。 给定数组可能包含重复元素，每个元素只可被选择一次 。请以列表形式返回这些组合，列表中不应包含重复组合。
/* 回溯算法：子集和 II */
void backtrack(List<Integer> currentSubset, int target, int[] options, int start, List<List<Integer>> results) {
// 子集和等于 target 时，记录解
if (target == 0) {
results.add(new ArrayList<>(currentSubset));
return;
}
// 遍历所有选择
// 剪枝二：从 start 开始遍历，避免生成重复子集
// 剪枝三：从 start 开始遍历，避免重复选择同一元素
for (int i = start; i < options.length; i++) {
// 剪枝一：若子集和超过 target ，则直接结束循环
// 这是因为数组已排序，后边元素更大，子集和一定超过 target
if (target - options[i] < 0) {
break;
}
// 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
if (i > start && options[i] == options[i - 1]) {
continue;
}
// 尝试：做出选择，更新 target 和 start
currentSubset.add(options[i]);
// 进行下一轮选择
backtrack(currentSubset, target - options[i], options, i + 1, results);
// 回退：撤销选择，恢复到之前的状态
currentSubset.remove(currentSubset.size() - 1);
}
}
/* 求解子集和 II */
List<List<Integer>> subsetSumII(int[] nums, int target) {
List<Integer> currentSubset = new ArrayList<>(); // 状态（子集）
Arrays.sort(nums); // 对 nums 进行排序
int start = 0; // 遍历起始点
List<List<Integer>> results = new ArrayList<>(); // 结果列表（子集列表）
backtrack(currentSubset, target, nums, start, results);
return results;
}
n 皇后问题
根据国际象棋的规则，皇后可以攻击与同处一行、一列或一条斜线上的棋子。给定 标签：搞定,target,nums,int,List,results,算法,回溯,new From： https://blog.csdn.net/2403_85375987/article/details/143666335