leetcode讲解_回溯 leetcode?

学这个东西，首先要有dfs的基础，明白凡是涉及回溯法的各种情况本质就是一个树。

回溯法是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。

回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态还原。

始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存状态。在具体的写法上，它在普通的深度优先搜索基础上的修改的步骤为[修改当前节点状态]→[递归子节点]→[回改当前节点状态]。

如果对那些遍历搜素“撞车”情况非常多，时间复杂度会很高。

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

注意：这里写按任意顺序

示例 1：

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

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

class Solution(object):
    def permute(self, nums):
        # 这题我们使用回溯法去处理，要想排列，首先要有树的概念，如果是三个数的话，那么我们就有三层的计算，两个数的话就二层
        def back(nums,level):
            # 如果我搜索到最深层：
            if level==len(nums)-1:
                # 这里我用python的话，需要写成nums[:]的形式，这样才可令当前nums的值被改变后的结果可以正常输出   
                ans.append(nums[:])
                # print(id(nums[:]),id(nums))
                # return list(nums)
            # 如果没到最后一层就一直搜索，怎么表示排列呢，由于只用排列而不是组合，那么通过每次的数的交换就可以模拟
            for i in range(level,len(nums)):
                nums[i],nums[level]=nums[level],nums[i]
                # 接着往下一层搜索就可以了
                back(nums,level+1)
                # 回溯
                nums[i],nums[level]=nums[level],nums[i]

        # answer是要求二维的注意
        ans=[]
        back(nums,0)
        return ans

nums[:] ，因为它有[:]，是复制的意思， 传值调用，修改的是仅仅是堆中的内容，用id()函数显示的话，一开始指针还会指向nums的原地址（子对象与原对象相同），后面我要更改我的排序值，id(nums[:])显示的地址就会发生变换。nums表示的是数组，所以是引用的意思，传址调用，所以在leetcode中由于它都把nums的地址给固定了，我要想在树的叶节点处把结果添加到我的结果数组中。如果我在这题的输入为[1,0]的话，最终结果应该为[[1,0],[1,0]]。而不是答案的[[1,0],[0,1]]

https://blog.csdn.net/Sunshine_Java_L/article/details/79123972
https://blog.csdn.net/qq_42053453/article/details/105875813
https://blog.csdn.net/qq_43230540/article/details/84788151
《谷歌高畅Leetcode刷题笔记》