算法之回溯算法

发布时间 2023-04-05 16:44:19作者: 菜小季

回溯法

含义:类似枚举,一层一层往下递归寻找答案,尝试搜索答案,如果找到了答案,则返回答案,并且寻找其他可能的答案。如果没找到,则像上一层递归寻找可能的答案。

回溯算法也是递归算法的一种。

为什么要回溯呢?或者说为什么用到回溯算法呢?

因为我们不是要找到一个排列就好了,而是需要找出所有满足条件的排列

当递归调用结束时,结束的是当前的递归分支,还需要去别的分支继续找

因此需要撤销当前的选择,回到选择前的状态,再选下一个选项,即进入下一个分支。

 

练习题:力扣22------括号生成

力扣-----78