01.回溯算法梳理

2023-03-04 约 697 字预计阅读 2 分钟次阅读

#Algorithm 算法 Algorithm - 回溯 learn.

summary-backtrack-labuladong && 回溯细分 id:: fa46fb8b-f417-4457-aae7-bcfacfda375d

递归回溯区别:回溯也用到递归，但是相比递归多了条件剪纸，结束条件等；而递归就是回调自身，斐波那契数列为例，不存在发现结果不对倒回去的步骤；回溯比如一个格子里走出去，走不通了回去继续换个路劲，一般要有个状态记录走过的
id:: 9374c530-4426-441e-8048-2362e98c3b7b

id:: 63f7088c-681a-4fae-a9f0-3712420bbe3c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:  // 组合的这all都满足，入口就是空也是
        result.add(路径)
        return

    for 选择 in 选择列表:
		// 剪枝: 比如同元素的组合 x>start nums[x]=numx[x-1] 跳过
        做选择
        backtrack(路径, 选择列表)
        撤销选择

id:: 63fc2cd5-d8c2-4e77-8486-b5713111d5bb #+BEGIN_QUERY {:title [:h5.font-bold.blue.opacity-40"3. query (and BFS (and dalg (not tpl)) )"] :query (and “回溯” (and “dalg” (not “tpl”)) ) :result-transform (fn [result] (sort-by( fn [h] (get h :db/id 1) ) > result)) :breadcrumb-show? false :collapsed? true } #+END_QUERY

leetcode – backtrace [[2023-02-23 Thu]] id:: 62360062-8288-4366-a172-6bcfff419cd2
78.子集

dalghot100

一系列问题-tip-hot100 [[2022-11-30 Wed]]

回溯回溯 1
- > 排列组合子集-汇总 dalg -tip- </a> <a class="indent1 subw8 blue width-13-hide " >😁</a><a class="indent1 subw8 gray width-18-hide underline DarkOrchid " >😭汇总</a><a class="indent1 subw gray width-3-hide underline red " >0</a> </html>
- 1. 组合和等于target 有重复、不可复选的组合、排列问题 [[$red]]==组合问题和子集问题等价== 参考此页
 2. 电话号码的字幕组合 — 和无重复数字组合一样，从0号开始，扫完进入下一轮，结束就是n到了size
 3. 括号生成括号生成这个理解 —
https://leetcode.cn/problems/permutations/

46.不同元素的全排列

dalg -tip- 回溯和子集比！1
- 47. 有相同元素的全排列
https://leetcode.cn/problems/n-queens/

5.n皇后问题

dalg -tip- 回溯回溯对比 0

目录

01.回溯算法梳理