自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:00，当前版本为作者最后更新于2022-04-22 22:14:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3623 枚举排列 題解

如果您做完了此题，您可以尝试：

B3621 枚举元组

B3622 枚举子集

B3624 猫粮规划

题目大概的意思就是从 $n$ 个人中选出 $k$ 人排列，输出所有的排列方案。

这和枚举元组和枚举子集不一样的是，一个人在一个方案中只能出现一次。

方法1： 枚举所有方案后排除非法方案。

我们可以直接枚举 $k$ 元组，然后将非法的方案剔除。

时间复杂度为 $O(n^k)$，无法胜任此题。

所以我们要想其他的方法。

方法2： 使用一种方法判断该数是否使用过。

我们可以用 $use$ 数组判断数字 $i$ 是否被使用过，如果使用过标记位 1。

在这个例子中，数字 1 和 2 已经被使用，所以对应的 $use$ 数组中全部标记 1，下次枚举是遇到 1 就可以直接跳过。

可以写一个 dfs 函数来完成此题。

• 定义数组 $a$ 存储枚举的数列，其中 $a_i$ 表示第 $i$ 位的数字；
• 定义数组 $use$ 记录已经使用过的数字，其中在 $use_i$ 中如果为 1 则为使用过，否则为未使用；
• 在发现 $use_i=0$ 时，把 $i$ 存入 $a_i$，将 $use_i$ 标记为 1，递归下一个数字，递归完成后要将 $use_i$ 标记为 0；

这就是我们的 dfs 函数。

管理员注：

由于课程需要本题不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】