回溯法回溯法简介

回溯法简介

回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。一旦不符合条件，那么就退回到上一个状态，省去了继续往下探索的时间。最基本的回溯法是在解空间中穷举所有的解。比如求序列[1,2,3]的全排列，那么我们可以画出一颗解空间树。