回溯法
Opened this issue · 0 comments
lovelmh13 commented
什么时候用回溯法
当看见题目中写着 1 <= nums.length <= 6
类似的很小的范围时(范围太大的话,超时超到爆),可能是因为复杂度很高,可以直接用回溯(穷举)法暴力破解。
当问所有的可能性的时候,可以使用回溯法。
回溯的基本框架
回溯法就是一个多枝树的递归
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
也不是必须这样写,不写 for ,只要让 backtrack 滚动起来,可以一直递归就行。
如果要求使用的数不重复,则先把数组排列好,按顺序搜索方便排除
出现在 leetcode 里字节前 100 道里的回溯相关的题:
参考:回溯算法详解