全排列与含重复数字的全排列

全排列与含重复数字的全排列

一、前言

在算法题中，排列问题一直都很常见：给定一组数字，让你生成它们的全部排列。它本身并不难，但当数组中包含重复数字时，就需要我们格外注意去重逻辑。

在这里，我将结合两段代码，为大家介绍如何分别解决：

1. 不含重复数字的全排列（LeetCode 46）
2. 含重复数字的全排列（LeetCode 47）

同时，我会加入一些个人思路和经验，以便让这段理解更深入、更有趣。

---

二、不含重复数字的全排列

1. 题目概述

• 题目： 不含重复数字的数组 nums ，返回所有可能的全排列，答案可以按任意顺序给出。
• 示例：

  输入：nums = [1, 2, 3]
  输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
  

2. 核心思路

因为给定的 nums 没有重复数字，我们在排列时不用担心重复组合的问题。最常见的做法就是：

1. 回溯（Backtracking）。
2. 交换或者使用标记数组来确定哪些数字被用过。
3. 不用特别的去重手段，因为 nums 保证互不相同。

思路点睛

• 用一个变量记录当前填到第几个位置（索引 i）。
• 不断在剩余的数字中选择一个数字放到 path[i] 里。
• 当所有位置都填完时，得到一个完整排列。

3. 代码示例

以下给出一种使用 set 的思路：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []n = len(nums)path = [0] * ndef dfs(i, s):# i 表示目前要填的位置，s 是当前可用数字集合if i == n:# 如果已经填满一个排列，加入结果res.append(path.copy())return# 在可用数字集中选择一个数字 x 放在 path[i] 位置for x in s:path[i] = xdfs(i + 1, s - {x})dfs(0, set(nums))return res

思考亮点：

• 这里用了一个 set 来存储剩余可用数字，每次递归都从中拿出一个数字，再用 s - {x} 剩下的数字继续递归；这样就不必显式地使用 visited 数组或交换操作。
• 由于题目保证 nums 无重复，因此可以放心使用 set，不会漏掉也不会多算。

---

三、含重复数字的全排列

1. 题目概述

• 题目： 给定一个可能包含重复数字的序列 nums，返回所有不重复的全排列（答案可按任意顺序给出）。
• 示例：

  输入：nums = [1,1,2]
  输出：[[1,1,2], [1,2,1], [2,1,1]]
  

2. 核心思路

和不含重复数字相比，这里最大的挑战是去重。
如果我们继续用上一节的 set 思路，这里就会有一些麻烦：当 nums 中存在多个相同的数字时，set(nums) 会直接把相同元素合并成一个，导致我们漏掉某些可行组合。所以就需要额外的去重机制。

具体做法

1. 先对 nums 排序（非常关键的准备工作）。
2. 回溯过程：
   • 用一个布尔数组 on_path 标记哪些元素已经使用过。
   • 在枚举时，如果发现当前元素与前一个元素相同，并且前一个元素并没有被使用，那么就跳过它（剪枝）。

去重原理：

• 当我们已经处理过 nums[j-1] 而它没有被用过，这意味着在这个分支中已经考虑过“用重复元素做下一步”的可能；如果我们再次选择和前一个相同的元素，只会生成重复的排列。

3. 代码示例

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# 1. 先排序，为后续去重做准备nums.sort()n = len(nums)ans = []path = [0] * n      # path[i] 表示排列的第 i 个数字on_path = [False] * n  # 用来标记 nums 中哪几个位置已被使用# i 表示当前要填第几个数字def dfs(i: int) -> None:if i == n:# 所有位置都填完了，保存结果ans.append(path.copy())return# 枚举可以放在第 i 个位置的 nums[j]for j in range(n):# 1) 如果 nums[j] 已使用，则跳过# 2) 如果当前 nums[j] == nums[j-1] 并且前一个 nums[j-1] 没用过，也跳过（去重）if on_path[j]:continueif j > 0 and nums[j] == nums[j - 1] and not on_path[j - 1]:continue# 做选择path[i] = nums[j]on_path[j] = Truedfs(i + 1)# 撤销选择on_path[j] = Falsedfs(0)return ans

思考亮点：

• 使用 nums.sort() 让重复数字相邻，从而配合 j > 0 and nums[j] == nums[j-1] and not on_path[j-1] 这行判断完成去重。
• 无需在 path 恢复现场，因为 path[i] 每次都会被覆盖掉。
• 合理利用了 on_path 数组，简单直观地标记哪些下标已经用过。

---

四、我的一些思考

“排列” 题看似基础，却是锻炼回溯思想的好方式。”

1. 回溯框架要熟练：

   • 每一次递归代表一道决策，用来选择把哪个元素放到当前空位。
   • 在做完选择后，立刻递归到下一层；返回时，再撤销当前决策。

2. 去重要尽早：

   • 越早剪枝，就越能提高效率。比如对数组排序能让相同数字相邻，从而在一次循环里轻松判断是否存在重复使用。

3. 细节决定成败：

   • 对于有重复的情况，一定要看清判断条件 nums[j] == nums[j - 1] and not on_path[j - 1]，这句是精华所在。

4. 题型扩展：

   • 如果需要全组合或含有一些额外限制的全排列，都可以在这个框架上加点改动。
   • 类似棋盘问题、走迷宫等，也会经常用到回溯 + 标记数组 + 剪枝的思路。

---

五、总结

• 回溯 是解决全排列问题的核心思路。
• 不含重复的情形可以简单地用一个 set 或 visited 数组来搞定；含重复的情况要依赖排序与剪枝逻辑。
• 代码虽短，但一定要对每一行的含义足够清楚，尤其是在“选和不选”的时机上要把握准确。

有时候，解决问题的关键不在于把代码写多长，而在于用最正确、简洁的方式表达逻辑。希望本文能给你带来一些启发，让你在面对类似的全排列、全组合题目时更加得心应手。

祝你在刷题的道路上越走越顺！

---

如果你对这篇博客或代码有任何想法，欢迎在评论区交流与探讨~