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]]

示例 2：

输入：nums = [0,1]

输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]

输出：[[1]]

思路分析

回溯找所有排列组合的可能。

在网上找了下面这个图，我觉得很清晰。

首先确定终止条件，显然，当我们排列组合的长度等于题目所给的长度的时候就结束，这也同时说明达到了叶子节点。

在这个过程我们需要记录已经使用过的数字，当前的结果集，还有总的结果集。

来一下过程模拟:

• 遍历到1，查看1是否使用过，看他是不是在used里面，不在，则加入used，加入当前结果集合path，然后递归调用本函数。
• 又遍历1，看他是否在used里面，显然在，结束本次循环，去遍历第二个数 2。 2不在used里面，所以加入used，加入当前结果集合path，然后递归调用本函数。
• 又遍历1，1在used里，遍历2，2也在used里，遍历3，3不在used里，所以3加入used，加入path。此时显然 path的长度已经等于题目所给的数组长度，则将此时path的答案加入最终答案集合，然后return函数， 开始回溯，将used回退，path回退，
• 这里因为遍历的是3，所以回退之后，当前的 循环也完成了，所以回退过程是 [1,2,3]->[1,2]->[1]，显然下一个遍历的数是3(刚才2已经遍历过了嘛)。这里说的可能比较乱，调试一下程序看看过程就清楚了。

递归中值和引用传递的问题。

# 递归的时候变量都保存在栈里，result里面存的是的地址。
      但是，当递归函数运行结束，就被pop掉了。
            # []是引用 传址调用  引用传递 
            # [:] 是复制 传值调用
            # 在这里 直接append也是空数据 而extend却可以
            # 说明append直接是传地址引用，当递归回去的时候引用被释放了，而extend是迭代值再添加属于值的使用。
            # 所以 切片也是复制的值传递  类似于 deepcopy？？      

完整代码

= []  # 中间结果集
        res = []  # 最终结果集
        temp = []  # 已经用过的数字记录

        def backtrack(num, temp):
            if len(path) == len(num):
                # 当前的中间结果已经满足条件 即长度一样了
                res.append(path[:])
                # res.extend(path)
                # res.append(path)
                return

            for i in range(len(num)):
                if num[i] in temp:
                    continue  # 如果当前数字在中间结果集中 表明当前数字已经用过了
                path.append(num[i])  # 加入中间结果集
                temp.append(num[i])  # 加入已用过数字记录集
                backtrack(num, temp)
                path.pop()
                temp.pop()

        backtrack(num, temp)
        return