回溯算法复习(1)
1.回溯的定义（ai）
回溯（Backtracking） 是一种通过搜索所有可能的解空间来求解问题的算法思想，属于试探性求解方法。其核心是在搜索过程中逐步构建解，并在发现当前路径无法得到有效解时，主动回退（回溯）到上一个可行状态，尝试其他路径，避免无效搜索。
回溯的基本概念
-
解空间
问题所有可能解的集合，通常以树形结构（如子集树、排列树）表示，每个节点代表一个部分解。 -
约束条件
用于判断当前部分解是否有潜力成为有效解的规则。若不满足约束条件，则跳过该分支（剪枝）。 -
状态树遍历
通过深度优先搜索（DFS）遍历状态树，从根节点出发，逐步扩展路径。若当前路径无法继续（达到叶节点或被剪枝），则回溯到上一层节点，尝试其他分支。
回溯的适用场景
回溯算法适用于有明确解空间且需要枚举所有可能解的问题，常见场景包括：
- 组合问题：如子集生成、组合数选取（例：从 n 个元素中选 k 个的所有组合）。
- 排列问题：如全排列、有重复元素的排列。
- 棋盘问题：如八皇后问题、数独求解。
- 路径搜索问题：如迷宫寻路、图的哈密顿路径。
- 约束满足问题：如符号方程求解、字符串匹配。
回溯的执行流程
- 初始化：从空解或初始状态开始，构建解的起始节点。
- 深度优先扩展：递归或迭代地向当前解中添加新元素，生成子节点。
- 约束检查：判断当前子节点是否满足所有约束条件：
- 若满足，继续递归搜索该子节点的子节点。
- 若不满足或已达叶节点（完整解），则回溯到父节点，尝试其他未探索的分支。
- 记录有效解：当找到完整且满足条件的解时，将其加入结果集。
回溯与剪枝
- 剪枝（Pruning）：在搜索过程中，通过约束条件提前排除无效分支，减少计算量。例如：
- 在子集和问题中，若当前子集的和已超过目标值，可直接跳过该分支。
- 在排列问题中，通过标记已使用的元素避免重复计算。
- 剪枝的关键：设计高效的约束条件，尽可能早地排除无效路径，提升算法效率
2.模板（代码随想录）
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果} }
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}作者：代码随想录
链接：https://leetcode.cn/problems/combinations/solutions/857507/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-0uql/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。第一步: 定义收集结果的集合
定义每个集合内的结果
第二步:定义起始值（防止出现重复集合）
第三步:寻找终止条件
题解：
class Solution {List<List<Integer> > res = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {if (k <= 0 || n < k) return res; // 处理边界条件combineHelper(n, k, 1); // 从1开始选择return res;}private void combineHelper(int n, int k, int startIndex) {if (path.size() == k) {res.add(new ArrayList<>(path)); // 深拷贝当前路径return;}int size = path.size();for (int i = startIndex; i <= n - (k - size) + 1; i++) {path.add(i);combineHelper(n, k, i + 1);path.remove(path.size() - 1); // 修正：删除最后一个元素}}
}从 i 到 n 的元素个数为 n - i + 1。
i = k-size
未剪枝优化
class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> path = new ArrayList<>();private int target;public List<List<Integer>> combine(int n, int k) {this.target = n;dfs(1,k);return ans;}public void dfs(int startx,int k ){if(k == 0){ans.add(new ArrayList<>(path));return ;}for(int i = startx;i<=target;i++){path.add(i);dfs(i+1,k-1);path.remove(path.size()-1);}}
}class Solution {List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return result;}public void backtracking(int n,int k,int startIndex){if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i =startIndex;i<=n;i++){path.add(i);backtracking(n,k,i+1);path.removeLast();}}
}