回溯算法复习(1)

1.回溯的定义（ai）

回溯（Backtracking） 是一种通过搜索所有可能的解空间来求解问题的算法思想，属于试探性求解方法。其核心是在搜索过程中逐步构建解，并在发现当前路径无法得到有效解时，主动回退（回溯）到上一个可行状态，尝试其他路径，避免无效搜索。

回溯的基本概念

1. 解空间
   问题所有可能解的集合，通常以树形结构（如子集树、排列树）表示，每个节点代表一个部分解。

2. 约束条件
   用于判断当前部分解是否有潜力成为有效解的规则。若不满足约束条件，则跳过该分支（剪枝）。

3. 状态树遍历
   通过深度优先搜索（DFS）遍历状态树，从根节点出发，逐步扩展路径。若当前路径无法继续（达到叶节点或被剪枝），则回溯到上一层节点，尝试其他分支。

回溯的适用场景

回溯算法适用于有明确解空间且需要枚举所有可能解的问题，常见场景包括：

• 组合问题：如子集生成、组合数选取（例：从 n 个元素中选 k 个的所有组合）。
• 排列问题：如全排列、有重复元素的排列。
• 棋盘问题：如八皇后问题、数独求解。
• 路径搜索问题：如迷宫寻路、图的哈密顿路径。
• 约束满足问题：如符号方程求解、字符串匹配。

回溯的执行流程

1. 初始化：从空解或初始状态开始，构建解的起始节点。
2. 深度优先扩展：递归或迭代地向当前解中添加新元素，生成子节点。
3. 约束检查：判断当前子节点是否满足所有约束条件：
   • 若满足，继续递归搜索该子节点的子节点。
   • 若不满足或已达叶节点（完整解），则回溯到父节点，尝试其他未探索的分支。
4. 记录有效解：当找到完整且满足条件的解时，将其加入结果集。

回溯与剪枝

• 剪枝（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();}}
}