回溯算法2s总结

8.回溯算法

回溯算法理论基础

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

组合是不强调元素顺序的，排列是强调元素顺序。

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法套路总结

回溯三部曲

• 回溯函数模板返回值以及参数

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数)

• 回溯函数终止条件

遍历树形结构一定有终止条件，回溯也有。什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

if (终止条件) {
    存放结果;
    return;
}

• 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，回溯不断调整结果集。这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法模板框架

分析完过程，回溯算法模板框架如下：

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

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

剪枝优化

剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够 题目要求的k个元素了，就没有必要搜索了

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

求组合

如果是一个集合来求组合的话，就需要startIndex，如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex

那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

**树层去重的话，需要对数组排序！**需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

其实切割问题类似组合问题。

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

Hjk最多几个直角三角形（我自己存在去重问题）

题目
我们手上有N条长度不等的线段，想知道我们能用这些线段组成多少个直角三角形。每条线段只能用一次，一个三角形由三条线段组成。

输入：

第一行是一个数字T，代表有T组数据。
在接下来的T行中，每一行的开始是一个数字N（代表线段的数量），后面跟着N个数字，代表每条线段的长度。
输出：

对于每一组数据，输出一行，表示我们可以组成的直角三角形数量。
示例：

输入:
1
7 3 4 5 6 5 12 13

输出:
2

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

bool isRightTriangle(int a, int b, int c) {
    std::vector<int> sides = {a, b, c};
    std::sort(sides.begin(), sides.end());
    return sides[0] * sides[0] + sides[1] * sides[1] == sides[2] * sides[2];
}

int countRightTriangles(std::vector<int>& sides) {
    int count = 0;
    int n = sides.size();
    std::vector<int> path;
    std::vector<bool> used(n, false);

    std::function<void(int)> backtrack = [&](int start) {
        if (path.size() == 3) {
            if (isRightTriangle(path[0], path[1], path[2])) {
                count++;
            }
            return;
        }

        for (int i = start; i < n; i++) {
            if (!used[i]) {  // Ensure each side is used at most once
                used[i] = true;
                path.push_back(sides[i]);
                backtrack(i + 1);
                path.pop_back();
                used[i] = false;
            }
        }
    };

    backtrack(0);
    return count;
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int N;
        std::cin >> N;
        std::vector<int> sides(N);
        for (int i = 0; i < N; ++i) {
            std::cin >> sides[i];
        }
        std::cout << countRightTriangles(sides) << std::endl;
    }
    return 0;
}