【深度优先搜索4】输出全排列

我们首先再回忆下DFS，以便解决这道题。

深度优先搜索（DFS）

深度优先搜索（DFS）的核心思想是沿着一条路径深入探索，直到无法继续时回退一步，尝试寻找其他未探索的路径。如果依然无路可走，就再次回退，重复这一过程，直到所有可能的路径都被探索完毕。

递归是深度优先搜索的常见实现方式。通过不断地调用自身函数，逐层深入解决问题。当满足终止条件时，停止递归并开始逐层回溯。递归的思想与深度优先搜索的探索与回溯过程高度一致，因此递归是实现深度优先搜索的常用方法。

我们通过一个例子来理解如何实现全排列：

样例1

3
1 2 3

步骤解析：

一：首先，三个位置都是空的，考虑填入 1，进入第二层。来到第二个位置有(2, 3)可以填，先选择填入 2，来到最后一个位置，只能填入 3，找到第一个符合的答案 1 2 3。

二：已经走到底了，向上回溯，来到 1 2，发现除了填入 3 没有其他操作了，继续向上回溯。接下来，我们回溯到 1，尝试填入 3，然后填入 2,得到 1 3 2。

接下来的回溯操作类似，直到所有排列都被找到。

题解

题面描述

给定一个整数数组 nums，其中包含 n 个互不相同的元素，要求输出该数组的所有可能排列（全排列），且排列结果按字典序排序。

思路分析

全排列的生成可以通过深度优先搜索（DFS）实现，利用回溯法探索所有可能的排列组合。以下是实现全排列的具体步骤：

1. 输入与初始化

首先，输入数组 nums：

n = int(input())  # 输入数组的长度
nums = list(map(int, input().split()))  # 输入数组

对数组排序，方便递归选择小的数向下递归，这样能确保生成排列的顺序是字典序最小开始：

# 按字典序排序
nums.sort()

准备辅助数据结构：

• path：保存当前路径，即当前排列。
• visited：布尔数组，用于标记数组中的每个元素是否已经被使用。
• result：存储所有生成的排列。

result = []  # 存储所有排列
path = []    # 当前路径
visited = [False] * n  # 标记每个数字是否被访问

2. DFS 递归函数

终止条件：

当路径长度等于数组长度时，表示生成了一个完整的排列，将当前路径存储到 result 中。

if len(path) == len(nums):
    result.append(path[:])  # 将当前路径加入结果
    return

向下递归：

从小到大遍历数组中未被使用的元素，尝试将其加入当前路径。

标记该元素为已使用，并递归调用函数以填充下一个位置。

向上回溯：

从递归返回后，将路径中最后加入的元素移除，并将该元素标记为未使用，以尝试其他选择。

for i in range(len(nums)):
    if not visited[i]:  # 如果当前数字未被访问
        visited[i] = True  # 标记为已访问
        path.append(nums[i])  # 加入路径
        dfs(nums, path, visited, result)  # 递归调用
        path.pop()  # 回溯，移除路径中的最后一个数字
        visited[i] = False  # 恢复标记为未访问

3. 字典序保证

在 DFS 前对数组排序，确保以字典序最小的排列开始。如果先DFS再对结果排序，时间复杂度相比前者增加许多，所以不采用。

通过有序遍历和回溯机制，最终生成的排列按字典序输出。

4. 输出结果

遍历存储结果的二维数组 result，逐行输出每个排列：

for perm in result:
    print(" ".join(map(str, perm)))  # 输出每个排列

完整代码

def dfs(nums, path, visited, result):
    # 终止条件：路径长度等于 nums 长度，说明一个排列生成完毕
    if len(path) == len(nums):
        result.append(path[:])  # 将当前路径加入结果
        return
    
    # 遍历每个元素，尝试加入当前路径
    for i in range(len(nums)):
        if not visited[i]:  # 如果当前数字未被访问
            visited[i] = True  # 标记为已访问
            path.append(nums[i])  # 将该数字加入路径
            dfs(nums, path, visited, result)  # 递归调用
            path.pop()  # 回溯，移除路径中的最后一个数字
            visited[i] = False  # 恢复标记为未访问

def main():
    # 读取输入
    n = int(input())  # 输入数组的长度
    nums = list(map(int, input().split()))  # 输入数组

    # 按字典序排序
    nums.sort()

    result = []  # 存储所有排列
    path = []    # 当前路径
    visited = [False] * n  # 标记每个数字是否被访问

    # 调用 DFS
    dfs(nums, path, visited, result)

    # 输出所有排列
    for perm in result:
        print(" ".join(map(str, perm)))  # 输出每个排列

if __name__ == "__main__":
    main()

题目描述：

给定一个包含 n 个不同整数的数组 nums，请你使用深度优先搜索（DFS）算法，输出数组中所有可能的排列结果。

排列中的每个元素必须是唯一的，按照字典序的顺序排列

输入：

• 第一行输入一个整数 n（1 ≤ n ≤ 9），表示数组中元素的个数。
• 第二行输入 n 个不同的整数，表示数组 nums 中的元素，数组中的元素均为整数，且满足绝对值不超过 $10^4$。

输出：

输出所有可能的排列，每行输出排列。排列中的数字间用空格隔开。

字典序说明:

对于两个不同的字符串，从左到右逐个比较它们的字符：

• 如果在某个位置上它们的字符不同，则将它们按照位置上的字符的字母顺序进行排序，即较小的字符排在前面，较大的字符排在后面。

• 如果一直比较到其中一个字符串结束，则较短的字符串排在前面；

• 如果两个字符串完全相同，则它们的字典序相同。可以将它们看作是按照字母表的顺序进行排序的。

本道题的把数组每个数字看作一个字符，通过字典序比较。

输入示例：

3
1 2 3

输出示例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1