全排列

题目描述

给定一个不含重复数字的数组 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]]

题解

本题是一个经典的回溯算法问题，我们可以使用深度优先搜索（DFS）的思想来解决。 我们从数组的第一个位置开始，依次枚举每个位置可以放置的数字，然后递归地进行下一层的搜索。当搜索到数组的最后一个位置时，我们将当前的排列加入到结果集中。

代码如下：

from typing import List
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(nums, path):
            if not nums:
                res.append(path)
                return
            for i in range(len(nums)):
                dfs(nums[:i] + nums[i+1:], path + [nums[i]])
        dfs(nums, [])
        return res

代码解释： 这里需要注意函数 dfs(nums[:i] + nums[i+1:], path + [nums[i]])：

• [:i]表示从第0个元素开始到第i-1个元素，不包括第i个元素

• [i+1:]表示从第i+1个元素开始到最后一个元素，包括第i+1个元素

• nums[:i] + nums[i+1:] 是递归时“去掉”当前选定数字后的剩余数字，这保证了每次递归时都不会选择已经选过的数字。

• path + [nums[i]] 是将当前选中的数字 nums[i] 加入到当前的排列路径 path 中，形成新的路径传递到下一层递归。

回溯的角度：

回溯的核心思想包括：选择-探索-回退

初始状态： nums = [1, 2, 3] path = [] (当前排列为空)

• 第一层递归： dfs(nums = [1, 2, 3], path = []) 在当前递归中，我们从 nums = [1, 2, 3] 中选择i=0的一个元素。 选择 1: 选择 1 后，新的 path = [1]，剩下的数字是 nums = [2, 3]，我们进入下一层递归。 调用 dfs(nums = [2, 3], path = [1])

  • 第二层递归： dfs(nums = [2, 3], path = [1]) 在当前递归中，我们从nums = [2, 3] 中选择i=0元素。 选择 2: 选择 2 后，新的 path = [1, 2]，剩下的数字是 nums = [3]，我们进入下一层递归。

    • 第三层递归： dfs(nums = [3], path = [1, 2]) 在当前递归中，我们从 nums = [3] 中选择i=0的元素。 选择 3: 选择 3 后，新的 path = [1, 2, 3]，剩下的数字是 nums = []，我们进入下一层递归。

      • 第四层递归： dfs(nums = [], path = [1, 2, 3]) 由于 nums = []，我们已经到达了递归的终止条件，将当前的 path = [1, 2, 3] 添加到结果集中。 回退到第三层递归：

    • 第三层递归： dfs(nums = [3], path = [1, 2]) 第三层的len(nums==1),故我们选择i=0的元素，已经没有i=1。 直接回退到第二层递归：

  • 第二层递归： dfs(nums = [2, 3], path = [1]) 我们选择i=1的元素即:3，新的 path = [1, 3]，剩下的数字是 nums = [2]，我们进入下一层递归。

    • 第三层递归： dfs(nums = [2], path = [1, 3]) 在当前递归中，我们从 nums = [2] 中选择i=0的元素。 选择 2:

      • 第四层递归： dfs(nums = [], path = [1, 3, 2]) 由于 nums = []，我们已经到达了递归的终止条件，将当前的 path = [1, 3, 2] 添加到结果集中。 回退到第三层递归：

      • 第三层递归： dfs(nums = [2], path = [1, 3]) 回退到第二层递归：

  • 第二层递归： dfs(nums = [2, 3], path = [1]) 由于第二层的len(nums==2),我们已经选择i=1的元素，没有i=2的元素，直接回退到第一层。 回退到第一层递归：

• 第一层递归： dfs(nums = [1, 2, 3], path = []) 我们选择i=1的元素 2，新的 path = [2]，剩下的数字是 nums = [1, 3]，我们进入下一层递归。

  • 第二层递归： dfs(nums = [1, 3], path = [2]) 在当前递归中，我们从 nums = [1, 3] 中选择i=0元素。 选择 1: 选择 1 后，新的 path = [2, 1]，剩下的数字是 nums = [3]，我们进入下一层递归。

    • 第三层递归： dfs(nums = [3], path = [2, 1]) 在当前递归中，我们从 nums = [3] 中选择i=0的元素。 选择 3: 选择 3 后，新的 path = [2, 1, 3]，剩下的数字是 nums = []，我们进入下一层递归。

      • 第四层递归： dfs(nums = [], path = [2, 1, 3]) 由于 nums = []，我们已经到达了递归的终止条件，将当前的 path = [2, 1, 3] 添加到结果集中。

......依次类推即可。