代码随想录09:回溯算法

BBigSun 评论197阅读模式

代码随想录09:回溯算法

什么是回溯法?

回溯法:回溯搜索法,是一种搜索方法,回溯是递归的副产品,只要有递归就会有回溯。文章源自十年又十年-https://www.bbigsun.com/416.html

回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案文章源自十年又十年-https://www.bbigsun.com/416.html

回溯法解决的问题

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里面有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独

组合无序,排列有序文章源自十年又十年-https://www.bbigsun.com/416.html

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}
文章源自十年又十年-https://www.bbigsun.com/416.html文章源自十年又十年-https://www.bbigsun.com/416.html

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 31日 08:29:56
  • 转载请务必保留本文链接:https://www.bbigsun.com/416.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定