写在前面
当前ai大模型迅速发展，单纯的刷题意义甚微。核心是掌握算法的思想，思想是永恒的，代码实现是暂时的。
本系列文章，旨在记录经典算法思想，不纠结于算法的实现细节问题。
回溯
回溯算法的核心是“深度优先搜索”使用递归来探索所有的解决方法，找到满足期望的解决方案。对于每个节点，算法都试图继续前进到下一个节点。如果一个节点发现自己走投无路（无法继续或者已经不满足约束条件），它就会回溯到上一个节点，然后尝试另一种可能的路线。
核心
DFS: 深度优先遍历
回溯: 理解为回退，走投无路时原路返回，返回上一个确定的决策点位。
组成部分
路径：已经做出的选择。
选择列表：你当前可以做的选择。
结束条件：决定是否已经达到了问题的解决方案。
算法流程
1.从决策树的根节点开始，树的深度表示问题解的阶段。
2.根据限制条件，尝试可能的所有选项（这通常用循环实现）。
3.继续向下递归，如果当前处理的节点满足边界约束，和条件约束，将当前节点添加到路径中（称为做出选择）。
4.按照深度优先的方式，继续递归，如果不符合条件或者已到达叶子节点（解的底部），则回溯到上一个节点，撤销上一步的选择，并执行其他可能的选择（称为撤销选择）。
5.重复以上步骤，直到找到所有解或遍历完所有可能的路径。
总结：流程核心为三点：最小计算因子、结束条件、以及回溯操作。
实际应用
回溯算法广泛应用于许多计算机科学问题中，包括但不限于：
1.排列组合问题:诸如括号对等。
2.解数独
3.N皇后问题
4.图的着色问题
5.旅行商问题（尝试解决方案并查找最优解）
6.找到所有子集的问题
相关算法
与回溯经常搭配使用的算法为剪枝算法。剪枝算法顾名思义：将已经确认不再符合需求的路径剪掉（回溯本身可以理解为对树的DFS,故用“剪枝”）。
case-study
- 给定一个正整数的输入数组与一个目标正整数，输出数组中所有累加和为目标正整数的排列组合，数字允许重复。
- 分析：典型的排列组合问题，优先应该使用回溯进行解决。从回溯算法的核心流程触发，思考几个问题：
- 最小计算因子是什么？
将数组中的数字进行相加 - 结束条件？
数字相加等于target - 回溯操作是什么？
条件满足&不满足，返回上一层时将之前加的数字去掉
根据上述思路，给出具体的实现细节，以java为例(语言真的一点儿都不重要):
public static void coreBackingTracing(List<List<Integer>> results, List<Integer> subResult, List<Integer> numbers, int target, int cursor) {//1.回溯终止条件if (target == 0) {results.add(new ArrayList<>(subResult));return;}if (target < 0) {return;}for (int i = cursor; i < numbers.size(); i++) {//2.最小计算因子subResult.add(numbers.get(i));coreBackingTracing(results, subResult, numbers, target - numbers.get(i), i);//3.回溯操作subResult.remove(subResult.size()-1);}}
尝试运行下：
List<List<Integer>> results = new ArrayList<>();List<Integer> numbers = new ArrayList<>();numbers.add(5);numbers.add(2);numbers.add(3);numbers.add(7);coreBackingTracing(results, new ArrayList<>(), numbers, 7, 0);System.out.println(results);
输出
[[5, 2], [2, 2, 3], [7]]
杂七杂八
再来点儿小小的头脑风暴，思考两个问题：
1.如果数字不允许重复，如何修改算法？
不允许重复，即在一次dfs递归中，元素被选择了一次后，不会再被选择：
coreBackingTracing(results, subResult, numbers, target - numbers.get(i), i+1);
2.该算法中还涉及到浅拷贝和深拷贝的基础问题：
if (target == 0) {results.add(new ArrayList<>(subResult)); //此处其实为浅拷贝，但是由于Integer为不可变类型，故效果等同深拷贝return;}
ps.贴个非常非常基础的浅拷贝和深拷贝概念：
- 浅拷贝：复制对象及其基本类型字段的值，但复制的是引用类型字段的引用而非引用对象本身。
- 深拷贝：复制对象及其内的所有对象，不论是基本类型字段还是引用类型字段，为后者创建完全独立的副本。
