排列型回溯

之前做算法题，如果在某个地方卡壳了，就会一直纠结那个步骤怎么实现，后面看答案也会困惑为什么要这样做，耽误了很多时间。刷了一段时间的题后，我总结出一个更高效的方法：先写一个实例，然后在纸上根据实例一步步推导答案，缺了什么变量，或者需要什么步骤，就在相应的地方加上，得到一个完整的流程，这样在写的时候会流畅很多，就算不会，后面看答案也能更快理解。

需要一个数组path记录每次选择。

第一次：1、2、3都可以选

第二次：如果选了1，那么下一步只能选择剩下的2、3

第三次：如果选了2，那么后面的就只能选择3

如果用for循环，每一次都从头开始选，会浪费很多时间。比如第一次选了[1、2、3]，第二次想选[1、3、2]，再从1开始循环，相当于重复了一步。

那有没有方法可以不从头开始，而是“回”到第二步呢，这里需要用到回溯递归。当下一步的递归到边界时，就返回上一步的下一个选择，继续递归。

所以需要一个递归函数dfs（i）；i代表了path下标，也代表了当前是哪一层的选择

但每一层的选择都需要重新遍历数组nums，那怎么知道哪些数已经选了呢，或者说如何跳过已经被选的数呢，一个个用if判断太麻烦了，所以还需要一个等长的判断数组on_path。当往path中加入num[j]时，就把相同下标的on_path[j]置为true，代表已经被选择。同时，当返回上一层选择时，也要把这一层置为true的on_path重新置为false，恢复现场。

那么总结以上流程，得到的代码如下：

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]: 
        n = len(nums)
        path = [0] * n  # 所有排列的长度都是一样的 n
        on_path = [False] * n
        ans = []

        def dfs(i:int)->None:
        	#递归停止的边界
            if i == n:
                ans.append(path.copy())
                return
  
            for j,on in enumerate(on_path):
                if not on:
                    path[i]=nums[j]
                    on_path[j]=True
                    dfs(i+1)
                    #当执行到这条语句时，说明dfs(i+1)的递归结束了，恢复第i层选的数，for循环选择下一个数
                    on_path[j]=False
        dfs(0)
        return ans  

Tip

为什么是ans.append(path.copy())而不是ans.append(path)？

path 是一个列表（list），Python 中，列表是可变对象；变量 path 存储的其实是列表对象在内存中的地址。
ans.append(path) 会把这个引用添加到 ans中。后续你在递归和回溯过程中不断修改 path[i]，由于 ans 中保存的所有引用都指向同一个列表对象，所以那些历史记录也会跟着“被修改”。

总结

总结排列型回溯的基本思路：

• 当前问题需要做什么
• 子问题需要做什么，如何进入子问题，子问题的子问题需要做什么
• 回溯的边界

我的很多思路都是向灵神学习的，也可以看他的视频[回溯算法套路③排列型回溯+N皇后【基础算法精讲 16】_哔哩哔哩_bilibili](https://)