python回溯算法重难点通俗讲解

重点就是找到回溯的条件
当不满足这个条件的时候，就回头

很多人都懂要回头走，但是怎么回头走？？？这个时候就把人分成了很多种：会回头的，不会回头走的，看了题解强行回头的。
这里拿LeetCode.46全排列做详解：
LeetCode.46 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # 所有数都填完了，结束点
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组，这里的满足条件是“无”
                nums[first], nums[i] = nums[i], nums[first]
                # 满足条件，继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作，不满足条件时，要把改变的nums变回原状
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

官方题解哈，回溯是怎么回头的其实就在这个for里面
当我们第一次执行这个for循环时，记为《第一次for》，第一次for满足backtrack（）函数的时候，就会进入第二个for循环《第二次for》，

重点来了，此时《第一次for》还没执行完！当我们执行完《第二次for》还没有满足backtrack的时候，就会执行还没执行完的《第一次for》

这就实现了回头。

看完了这里想必你已经懂怎么回溯了，别急，下面还有一个重点：

解决了疑惑的小朋友，不要吝惜右下角的小拇猪。

吐槽一下，可能博主太菜了，这个回溯，学了几天才恍然醒悟，看了好多csdn的文章，又去小破站看了好多up主视屏都没懂这个回溯是怎么回头的，终于，在一个夜黑风高的晚上，身体受了巨大的刺激，强行理解了回溯。