回溯、深搜、剪枝的区别是什么？

Question

在刷题中，看题解时总是遇到DFS、回溯、剪枝这类字眼，但总是搞不懂他们有什么区别。

以下是我的理解，不知是否正确？

剪枝是用来优化的，深搜是将一种可能执行到底，而回溯是碰到不可行的情况就结束，开始下次遍历， 那么深搜+剪枝=回溯。

Answer 1

以下是我个人理解：

深搜可以理解为一直套用函数最后得出结果；

回溯可以理解为对每一步或每一个位置上的不同操作的出多种结果，再根据所需取得想要的答案；

剪枝就是对递归函数空间和时间上的优化，舍掉无用部分的递归，尽力去只递归有价值部分。