46. 全排列

方法

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:# 方法1：可以用树去理解这个过程，看下面画的图def backtrack(first=0):# 如果第一个索引等于数组长度，说明找到了一个完整的排列if first == n:output.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]output = []n = len(nums)backtrack()return output# # 方法2：直接调包# from itertools import permutations# 因为permutations返回的是一个迭代器，所以要用list来把迭代器的所有结果都呈现出来# return list(permutations(nums))    # # 方法3：回溯，可以用树来理解这个过程，看下面的图# 方法3和方法1差不多，只是方法3每次传进去的参数都是list，而不是idx，可能会更占空间# # 递归法# result = []# def backtrack(current, remaining):#     if not remaining:#         result.append(current)#         return#     for i in range(len(remaining)):#         backtrack(current + [remaining[i]], remaining[:i] + remaining[i+1:])# backtrack([], nums)# return result

递归的步骤

1. 找到递归的出口
2. 抽象出递归函数的功能
3. 检查f(n-1)能否正常运行
4. 检查f(n)能否正常运行

回溯和递归的关系

回溯算法和递归是密切相关的概念，它们经常一起使用来解决问题。下面是它们之间的关系和区别：

递归（Recursion）

递归是一种编程技术，它允许一个函数直接或间接地调用自身。递归通常用于解决那些可以分解为更小的、相似的子问题的问题。

递归的特点：

1. 基本案例：递归函数必须有一个或多个基本案例，即递归结束的条件。
2. 递归步骤：函数通过调用自身来解决问题的更小部分。
3. 返回值：递归函数通常需要返回一个值。

回溯算法（Backtracking）

回溯算法是一种通过试错的方法来解决问题的算法。如果一个候选解最终被确认不是一个有效的解，回溯算法会丢弃它，并且回退到上一步，然后继续寻找下一个候选解。

回溯算法的特点：

1. 试错：尝试分步的去解决一个问题。在每一步中，算法会做出选择，并继续往下走。
2. 撤销操作：如果发现当前选择不能得到有效的解，算法会撤销上一步甚至是上几步的计算，再通过其他的可能的选项继续寻找解。
3. 剪枝：在搜索过程中，回溯算法可以剪去那些肯定不会产生有效解的路径，以减少计算量。

回溯和递归的关系

1. 递归是实现回溯的工具：回溯算法通常通过递归函数实现。递归函数可以方便地实现回溯算法中的撤销操作。
2. 回溯是递归的应用场景：递归本身是一种通用的编程技术，而回溯是递归在解决特定问题（如组合问题、排列问题、分割问题等）时的一种策略。
3. 回溯中的递归通常是有条件的：在回溯算法中，递归调用通常是有条件的，只有满足特定条件时才会进行递归调用。
4. 回溯中的递归包含撤销操作：在回溯算法中，递归调用后通常需要撤销某些操作（如交换元素位置），以便回溯到上一步。

示例

在全排列问题中，我们使用递归函数来探索每一种可能的排列，递归的每一步都对应着一个元素的选择。当我们发现当前选择不会产生有效排列时，我们会撤销这个选择（即回溯），然后尝试下一个元素。

总结来说，递归是回溯算法实现的技术手段，而回溯是递归在解决某些特定问题时的策略和方法。