回溯算法 深度优先搜索(dfs)_dfs算法怎么回溯

2023.11.14

终止条件
        一般是遍历到的节点个数等于预期，则程序终止，返回，不再递归调用
        此外，若只需要返回最优解时，则可以追加终止条件，程序只保存当下的最优解。
        若经判断不是最优解，则跳过。如有新的最优解出现时，则覆盖。
选择循环
        最笨的，每次遍历都循环所有节点。
剪枝操作
        当已经可以判断不满足题意时，跳过后续递归
递归调用
        将当前节点，满足条件的值，带入下一轮递归调用。重复上述过程，直至满足终止条件后返回。
路径弹出(栈)
        将当前的完整路径存入结果集，弹出最后一个节点。

经典例题：
        全排列：输入一个正整数m，求正整数序列[1,2,3,...,m]的所有排列                  

m = 5
 
paths = []
path = []
def dfs():
    global path
    if len(path) == m:               # 终止条件
        paths.append(path[:])
        return
    for i in range(1, m + 1):        # 选择循环
        if i in path:                
            continue                 # 剪枝操作
        path.append(i)               # 选中
        dfs()                        # 递归调用
        path.pop()                   # 弹出
 
dfs()                                #  关于参数列表，可因题意变化而修改。 
print(paths)

                       n皇后

参考文章：
五大算法思想（三）回溯法及常见例子_回溯算法几个经典例子-CSDN博客

===========================分割线======================================

下面来看一下OD真题，思路来自参考问章的博主大佬。
在自己尝试写的时候有以下几个注意点，
以及在啃大佬的代码时候有想为什么一定要写成这样而写成别的不行。

由题意，需要用到所有的数字，所以可以确定上升楼层的个数，作为返回条件。
由题意，想要找到不超过期望楼层的，将大于期望楼层的结果剪枝掉。
由题意，想要打印排序后的序列，即需要存储哪些上升，哪些下降，而不能单纯的排序上升楼层。
（在这个点上博主大佬用了[False] * n     确实惊艳到本菜鸡了 看大佬的思路能学到很多东西）

一开始不太熟回溯算法的写法，踩了点坑，是关于终止条件的写的位置。
由于每次递归调用时会将cnt + 1， 而终止条件是判断cnt是否等于要求的值。
所以要一进来就先判断，如果达到则return出去，如果不达到，则循环，不被剪枝后递归调用。
之前错误地将return判断写到for循环内了，会很容易导致剪枝continue和返回return的逻辑混乱。

由题意，只需要返回：等于期望楼层的解，若没有，则返回低于且最接近期望楼层的解。
不论哪种情况，返回paths内的每一项path，他们各自的和，应该是相同的。
因此当出现了新的最接近期望楼层的解的时候，要把原paths清空掉
再把当前的解写入paths，保证paths内所有的解的和都是相同的楼层。

所谓回溯，是要在当前节点的逻辑执行完毕后，将当前节点弹出。
全排列中用的是： for(): path.append()    dfs()    path.pop()
本题中用的是： for(): path[i] = True   dfs(path)   path[i] = False|
由此可得对dfs是，暂定当前节点满足要求，以此为前提，去向下延伸寻找可能解
也就对应了上文，终止条件的判断要写在for外，如果达到则return，这样进到for内就全都是需要向下查找的。

剪枝条件 up_total - (sum(arr) - up_total) > m
应变化为 up_total_max = (sum(arr) + m) // 2     up_total > up_total_max
抽出变量up_total_max，否则原用例将有4组超时TLE

至于最后的seqs.sort()，这里是需要做sort的，不加会有7个用例WA
分别是#6，#13，#16，#17，#18，#19，#23
我试着拿到了#23的用例，m = 7, n = 5, arr = [ 6, 4, 3, 1, 2 ]
此时seqs = [ [6, 3, 4, 2, 1],  [6, 4, 3, 1, 2] ]
若不加sort() 则输出[6,3,4,2,1] 加了sort()后， 输出[6,4,3,1,2]
按照paths的顺序转换过来的seqs，是按照上升序列大值优先的。
而本题返回期待的是seq的大值优先。
二者是有区别的，所以一定要加seqs.sort(reverse=True)，输出seqs[0]

以上。

参考文章：

华为OD机试 - 乘坐保密电梯（Java & JS & Python）-CSDN博客

2023.12.01

dfs 华为OD机试 - 篮球比赛（Java & JS & Python & C）-CSDN博客

排列问题是可以视为树的遍历的

递归调用的参数一般为：
        深度：作为返回条件
        结果值： 若结果是列表，则将引用经每一轮变换后再传递给下一轮，使得最终return时变量内存放的就是结果
        每一轮的传入：包括当前开始的索引，投入这一轮的数据集

2023.12.25
https://fcqian.blog.csdn.net/article/details/127711587
区别于前一道题取10取5的部分元素组合，这里用了全局变量used来控制全部元素取到。
对于入参内的重复元素，
在题解的正确性上，需要保证不重复：index不同 值相同的几个元素，产生的相同题解，只算一次
（eg：假设有5个元素且0号元素和1号元素的值一样，那么01xxx和10xxx的排列结果是等效的）
本题单使用全局used无法忽略这种结果上的重复，因为used是指向index的，所以需要借助集合来缓冲去重，再进行打印输出。
而在程序的效率上，这种重复出现的元素节点刚好是剪枝操作的关键

最后的sorted循环，首先，本题用例输入时是有大小写的，比如字典顺排序['A', 'B', 'a', 'b']
根据程序执行的过程，会依次将ABab, ABba, AaBb, AabB, AbBa, AbaB加进集合
饭于是我刨根问底一下去模拟了这个过程，输出每一次的集合状态

set1 = set()
set1.add('ABab')
print(set1)         # {'ABab'}
set1.add('ABba')
print(set1)         # {'ABba', 'ABab'}
set1.add('AaBb')
print(set1)         # {'AaBb', 'ABba', 'ABab'}
set1.add('AabB')    
print(set1)         # {'AabB', 'AaBb', 'ABba', 'ABab'}
                    # 直到这里都还可以理解，新输入的被放在了前面
set1.add('AbBa')
print(set1)         # {'ABba', 'ABab', 'AabB', 'AbBa', 'AaBb'}
                    # 这里就开始乱搞了
set1.add('AbaB')
print(set1)         # {'ABba', 'ABab', 'AabB', 'AbBa', 'AbaB', 'AaBb'}

反复执行的结果是一致的。虽然早就知道set是无序的但是不知道为什么，也没有多考虑。
现在看来，推测是集合内部可能有它自己的规则吧。（回头可以去查一下集合的底层来填个坑）
 

噢对，补上一句，由这个全局变量而突然更理解了，深度优先遍历是借用递归循环调用的串行方法，不是同时求组多组解的，相当于一个一个去尝试~结果满足，记录，回溯，结果不满足则直接回溯，直至查找全部完成，或触发了其他的终止条件。