C++基础算法 | 回溯算法（Back Tracking Method）&& 深度优先搜索（Depth First Search）_深搜回溯c++

C++基础算法 | 回溯算法（Back Tracking Method）&& 深度优先搜索（Depth First Search）

回溯与DFS的关系：回溯算法是一种通用算法。深度优先算法是一种特殊的回溯算法，应用于图搜索、树结构。

回溯与BFS的关系：BackTracking第一步先判断终止条件，BFS在出队列后先判断终止条件

回溯法有“通用的解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于解组合数较大的问题。