【代码随想录 回溯问题 总结】

本文总结了代码随想录 回溯章节内容

代码随想录 回溯问题 总结

• • 回溯模板
  • 无序
  • • 1. 组合问题
    • 2. 切割问题
    • 3. 子集问题
    • 4. 总结
  • 有序

回溯模板

void backtracking(参数) {
    if (终止条件) {
        收集结果;
        return;
    }

    for (选择：本层集合元素) {    // 树中子节点的数量就是集合的大小
        处理节点;
        backtracking();         // 递归
        回溯 *** 作;               // 撤销处理结果
    }
}

无序

每次递归从 startIndex 开始，因为该层取过的元素会对下一层可取的范围产生影响。

1. 组合问题

• 终止条件: startIndex == nums.size()
  因为nums最大的指数是nums.size() - 1, 超过该值无值可取
• 每层从 [startIndex, i] 区间中选取一个元素作为该层结果，本层之间不能重复。
  排序后，startIndex为每层开始的位置，只有大于该索引且数组前一个元素与当前相同，才是层内重复，需要跳过。

sort(nums.begin(), nums.end());
if (i > startIndex && nums[i] == nums[i-1]) continue; // 排除本层重复元素

• 若下一层不可重复取nums中的元素，下一次递归从 i + 1 开始。
• 若下一层可以重复取， 下一层递归从 i 开始。
• 可能有剪枝， 结果收集树的叶节点。

2. 切割问题

• 终止条件： 已经切到最末尾，startIndex == nums.size()
• 每层截取 [startIndex, i] 区间为子串或子区间
• 每次截取位置必定不同，下一次递归从 i + 1 开始。
• 有一个函数（一般bool）来判断子串是否符合题目要求，是否加入结果。
• 可能有剪枝，结果收集树的叶节点。

3. 子集问题

• 下一次递归从 i + 1 开始，无剪枝，遍历整棵树。
• 结果收集树的所有节点。

4. 总结

• 收集叶节点，终止时，res.push_back(path);
  收集所有节点，每次递归都推入结果。

• 下一层递归可重复选取数组元素：递归从 i 开始。
  下一层不可重复选取元素、不可截取同一位置：递归从 i + 1开始。

• 求和问题中, 常用排序和剪枝
  升序排列, 使相同的值挨在一起, 若小值求和已经大于 targetSum , 本层可以停止遍历, 即剪枝。
  这里只用一个变量不断求差, 保证差 >= 0。

sort(candidates.begin(), candidates.end());
for (int i = startIndex; i < candidates.size() && target - candidates[i] >= 0; i++) {}

有序

每次递归无需startIndex, 而是从 0 开始。因为元素顺序不同， 结果也不同。前一次的递归的选择元素不会对下一次可选元素范围造成影响。