登录以参加训练计划

搜索与回溯本质就是选择，在众多（一般用循环）可能的选择中选择一种，一直走下去，走不通，或者不符合条件，就回溯，选择下一种情况，直到所有情况遍历完，找到自己想要的结果或者方案。本质上也是一种暴力算法。因此在使用这种算法时一定要注意数据范围，基本上递归深度超过30了，会超时，需要再寻找其它算法。

1，什么是搜索算法

搜索算法是指在数据结构中寻找特定元素或解决方案的过程。它可以是简单的线性搜索（例如在数组中查找一个值），也可以是更复杂的如深度优先搜索（DFS）或广度优先搜索（BFS）。搜索算法试图遍历所有可能的解决方案，以找到符合条件的答案。

2，回溯算法

回溯算法是一种特殊的搜索算法，它不仅搜索解空间树，而且在搜索过程中会注销那些不会导致有效结果的选择。回溯算法通常用于解决组合问题，其中解是一个逐步构建的过程。当构建过程中的部分解被证明是无效的，算法就会回溯到最近的决策点，并尝试不同的选择。

3，搜索与回溯应用场景

搜索与回溯算法主要解决以下问题：

(1)棋盘类问题：例如八皇后问题、马走日、数独、图着色问题等。

(2)排列组合问题：找出符合条件的排列与组合问题等。

(3)路径寻找问题：迷宫问题、最短路径问题等。

注意： 搜索与回溯算法，有三个重要的概念：路径、选择、结束条件。它的整个执行过程其实就是建立了一个N叉树，路径是这个N叉树已经构建的部分，选择列表就是后续生长的部分，结束条件即到达叶子结点。

搜索与回溯的算法框架如下：

int search(int k) {
  for(int i=1;i<=选择种类数;i++){
    if (满足条件){
      保存结果//一般为标记状态，后面需要回退
      if (到达目的地或找到方案) 输出结果;
      else search(k+1);
      回退if前面的保存//回溯； 
    }    
  }
}

if (到目的地或者找到解决方案）{
  输出结果；
}else{
  for(int i=1;i<=可选方案;i++){
    if (满足条件){
      保存结果；
      search(k+1);
      恢复结果;//回溯。
    }
  }
}

因此，对于算法的核心，我们需要根据问题确定需要定义哪些变量来存储状态；递归函数的参数有哪些？递归的结束条件是什么？边界值是什么？是否需要记录求解的中间数据等。

4，回溯算法什么时候需要回溯，什么时候不需要回溯？

需要回溯的情况：

1. 需要找到所有可能的解，比如全排列、组合问题。
2. 路径探索问题，比如迷宫的所有路径。
3. 当需要穷举所有可能性，并且在尝试一种可能性后需要撤销状态，回到之前的状态尝试其他可能性。（比如n皇后）

​不需要回溯的情况：

1. 只需要找到一个解，或者最优解，比如最短路径问题。
2. 状态一旦确定就不会改变，比如某些动态规划问题。
3. 使用贪心算法时，每一步都做出当前最优选择，不需要回退。

总结：有时候即使是在需要找到所有解的情况下，如果状态可以共享或者不需要修改全局状态，也可能不需要显式的回溯。比如在分治法中，每次递归调用处理子问题，不会影响到其他子问题的处理，所以不需要回溯。

还有一个可能的混淆点是，递归本身的结构和回溯的关系。递归调用自然会有调用栈来保存状态，但显式的回溯（比如修改全局变量后恢复）需要在递归返回后手动处理。

比如在八皇后问题中，放置一个皇后后，需要标记该位置，然后递归处理下一行。处理完所有可能的下一行后，需要撤销当前皇后的放置（回溯），以尝试其他位置。这时候就需要显式的回溯。

而在计算斐波那契数列时，递归调用不需要修改任何全局状态，只是返回值，所以不需要回溯。

所以，总结一下，回溯的必要性取决于是否需要维护和恢复状态以尝试不同的可能性。如果问题需要遍历所有可能的分支，并且这些分支共享某些状态，就需要回溯来确保每个分支的独立性。

另外，代码结构的不同也会影响是否需要显式的回溯。比如，使用参数传递状态而不是修改全局变量，可能减少需要显式回溯的情况。因为每次递归调用都有自己的参数副本，不会影响到其他调用。