LeetCode-Go 题解精讲47. Permutations II 含重复元素的全排列去重排序 DFS 剪枝【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 47 题「Permutations II全排列 II」展开讲解在给定序列可能包含重复元素的前提下如何用 Go 语言通过「先排序、再 DFS 回溯、配合 used 数组剪枝」的思路输出所有不重复的全排列。读完本文你将掌握去重排列的经典写法、与第 46 题「Permutations」的差异点以及该解法在当前 LeetCode-Go 仓库中的完整实现与测试验证方式可以直接照搬代码并自行运行验证。一、题目回顾从「无重复」到「可能重复」题目原文如下Given a collection of numbers that might contain duplicates, return all possible unique permutations.即给定一个可能包含重复数字的序列返回所有不重复的全排列。题目给出的示例Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]这里的关键约束有两个输入数组可能含有重复元素如示例中的两个1输出结果必须去重即每个排列组合只能出现一次。如果按朴素的全排列思路直接枚举[1,1,2]会得到 6 个排列其中[1,1,2]、[1,2,1]、[2,1,1]各出现两次。题目要求输出 3 个唯一排列因此去重是本题的核心。仓库中对应的题目说明见 leetcode/0047.Permutations-II/README.md其中明确写到这一题是第 46 题的加强版第 46 题中数组元素不重复而这一题数组元素会重复所以最终排列出来的结果需要去重。二、解题思路总览排序 DFS used 剪枝原文档给出的解题思路可以归纳为三条本题是第 46 题的加强版。第 46 题46. Permutations求的是无重复元素数组的全排列本题元素可能重复因此需要在枚举过程中去除由重复元素带来的重复排列。去重方法是经典逻辑先把数组排序让重复元素相邻再做逻辑判断剪枝。其余思路与第 46 题完全一致使用 DFS 深搜回溯。整体流程为对nums做一次sort.Ints排序使相同元素相邻这是去重的前提维护used []bool记录每个下标在当前递归路径中是否已被选取维护p []int记录当前正在构造的排列前缀通过递归DFS在每一层尝试选取一个「未被使用」的元素在选取时加入剪枝条件若当前元素与前一元素相等且前一元素尚未被使用则跳过从而保证相同值的元素只会按固定顺序被选取一次避免产生重复排列。三、完整 Go 实现继承自原文档原文档给出的核心代码如下仓库中的实现源码见 leetcode/0047.Permutations-II/47. Permutations II.gopackage leetcode import sort func permuteUnique(nums []int) [][]int { if len(nums) 0 { return [][]int{} } used, p, res : make([]bool, len(nums)), []int{}, [][]int{} sort.Ints(nums) // 这里是去重的关键逻辑 generatePermutation47(nums, 0, p, res, used) return res } func generatePermutation47(nums []int, index int, p []int, res *[][]int, used *[]bool) { if index len(nums) { temp : make([]int, len(p)) copy(temp, p) *res append(*res, temp) return } for i : 0; i len(nums); i { if !(*used)[i] { if i 0 nums[i] nums[i-1] !(*used)[i-1] { // 这里是去重的关键逻辑 continue } (*used)[i] true p append(p, nums[i]) generatePermutation47(nums, index1, p, res, used) p p[:len(p)-1] (*used)[i] false } } return }3.1 入口函数 permuteUnique 逐行解读if len(nums) 0 { return [][]int{} }空数组直接返回空结果避免后续下标访问越界used长度与nums相同的布尔数组标记每个下标是否已被当前排列路径使用p当前正在构造的排列前缀res最终结果集合类型为[][]intsort.Ints(nums)对输入排序使重复元素相邻。排序是去重能够成立的前提——只有让相同的值排在一起剪枝条件才能通过“相邻比较”识别出重复随后调用generatePermutation47开始 DFS最终返回res。3.2 递归函数 generatePermutation47 的核心逻辑终止条件index len(nums)时说明已经选满了 n 个元素。此时需要把p拷贝一份copy(temp, p)再追加到res因为p在后续回溯中会被复用和修改不能直接引用遍历选取每一层从0到len(nums)-1尝试所有下标!(*used)[i]保证同一路径内不重复选取同一个下标去重剪枝最关键的一行if i 0 nums[i] nums[i-1] !(*used)[i-1] { continue }i 0防止对第一个元素访问nums[i-1]越界nums[i] nums[i-1]当前元素与前一个元素值相同说明遇到了重复元素!(*used)[i-1]前一个相同元素尚未被使用。结合“排序后相同元素相邻”的前提这表示在当前层之前相同值的元素还没有被选取过。此时若再选取nums[i]就会产生与先选nums[i-1]完全相同的排列分支因此直接剪枝跳过。这条条件的本质是规定相同值的多个元素必须按下标顺序依次被选取先取前一个才允许取后一个从而把重复元素产生的对称分支合并为一条从根源上杜绝重复排列而不需要最后再对结果做一次全局去重。回溯选取元素后递归进入下一层递归返回后执行p p[:len(p)-1]撤销选取并把(*used)[i] false释放下标恢复现场以便尝试其他分支。四、与第 46 题Permutations的对比原文档明确指出本题是第 46 题的加强版。对比仓库中两份实现可以直观看到差异第 46 题的 DFS 循环体leetcode/0046.Permutations/46. Permutations.go只有if !(*used)[i] { (*used)[i] true p append(p, nums[i]) generatePermutation(nums, index1, p, res, used) p p[:len(p)-1] (*used)[i] false }即无重复前提下只需保证「每个下标只用一次」即可枚举出全部 n! 个排列。第 47 题在同样的框架上增加两处去重设施入口处sort.Ints(nums)循环体内的相邻重复剪枝判断if i 0 nums[i] nums[i-1] !(*used)[i-1] { continue }。其余结构used 标记、p 前缀、递归终止拷贝、回溯复位完全一致。因此从源码结构可以推断掌握第 46 题的 DFS 框架后只需理解「排序 相邻重复剪枝」这一条规则就能自然迁移到本题。五、仓库测试用例验证去重正确性仓库为该题提供了完整的表驱动测试见 leetcode/0047.Permutations-II/47. Permutations II_test.go共覆盖 4 组输入输入期望输出覆盖意图[1, 1, 2][[1 1 2] [1 2 1] [2 1 1]]题目标准示例两个重复元素1[1, 2, 2][[1 2 2] [2 2 1] [2 1 2]]重复元素位于尾部验证剪枝在不同位置的正确性[2, 2, 2][[2 2 2]]全部元素相同全排列退化为仅 1 个结果[][]空数组边界验证入口处的空值保护这四组用例分别覆盖了「重复在头部」「重复在尾部」「全重复」「空输入」四种典型场景可以有效验证去重剪枝逻辑的正确性与边界安全。测试函数通过question47结构体组织参数与期望答案循环打印输入输出fmt.Printf(【input】:%v 【output】:%v\n, p, permuteUnique(p.s))测试运行命令与仓库 gotest.sh 中使用的命令一致该脚本同时以 atomic 模式生成覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只运行本目录下的测试go test ./leetcode/0047.Permutations-II/...六、复杂度与空间分析以仓库实现为准进行推断时间复杂度最坏情况下所有元素互不相同退化为第 46 题全排列数量为 n!每个排列需要 O(n) 时间拷贝入结果因此为O(n × n!)。当存在大量重复元素时剪枝会显著减少实际枚举的分支数例如[2,2,2]只产生 1 个结果而非 6 个分支。空间复杂度递归深度为 O(n)调用栈p与used均为 O(n)结果集本身需要存储 O(n × n!) 的空间该部分不计入辅助空间时可视为 O(n)。七、小结与延伸本题的完整脉络可以概括为一条主线排序使重复相邻 → DFS 按层选取 → 相邻重复且前驱未选则剪枝 → 回溯复位。这条「排序 used 前驱剪枝」的组合拳是含重复元素组合类/排列类问题如子集 II、组合总和 II 等的通用套路值得反复推敲。相关的仓库资料索引题目说明文档中文版leetcode/0047.Permutations-II/README.md英文版题目文档website/content.en/ChapterFour/0001~0099/0047.Permutations-II.md实现源码leetcode/0047.Permutations-II/47. Permutations II.go测试用例leetcode/0047.Permutations-II/47. Permutations II_test.go无重复版本对照实现leetcode/0046.Permutations/46. Permutations.go【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解精讲：47. Permutations II 含重复元素的全排列去重（排序 + DFS 剪枝）
LeetCode-Go 题解精讲47. Permutations II 含重复元素的全排列去重排序 DFS 剪枝【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 47 题「Permutations II全排列 II」展开讲解在给定序列可能包含重复元素的前提下如何用 Go 语言通过「先排序、再 DFS 回溯、配合 used 数组剪枝」的思路输出所有不重复的全排列。读完本文你将掌握去重排列的经典写法、与第 46 题「Permutations」的差异点以及该解法在当前 LeetCode-Go 仓库中的完整实现与测试验证方式可以直接照搬代码并自行运行验证。一、题目回顾从「无重复」到「可能重复」题目原文如下Given a collection of numbers that might contain duplicates, return all possible unique permutations.即给定一个可能包含重复数字的序列返回所有不重复的全排列。题目给出的示例Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]这里的关键约束有两个输入数组可能含有重复元素如示例中的两个1输出结果必须去重即每个排列组合只能出现一次。如果按朴素的全排列思路直接枚举[1,1,2]会得到 6 个排列其中[1,1,2]、[1,2,1]、[2,1,1]各出现两次。题目要求输出 3 个唯一排列因此去重是本题的核心。仓库中对应的题目说明见 leetcode/0047.Permutations-II/README.md其中明确写到这一题是第 46 题的加强版第 46 题中数组元素不重复而这一题数组元素会重复所以最终排列出来的结果需要去重。二、解题思路总览排序 DFS used 剪枝原文档给出的解题思路可以归纳为三条本题是第 46 题的加强版。第 46 题46. Permutations求的是无重复元素数组的全排列本题元素可能重复因此需要在枚举过程中去除由重复元素带来的重复排列。去重方法是经典逻辑先把数组排序让重复元素相邻再做逻辑判断剪枝。其余思路与第 46 题完全一致使用 DFS 深搜回溯。整体流程为对nums做一次sort.Ints排序使相同元素相邻这是去重的前提维护used []bool记录每个下标在当前递归路径中是否已被选取维护p []int记录当前正在构造的排列前缀通过递归DFS在每一层尝试选取一个「未被使用」的元素在选取时加入剪枝条件若当前元素与前一元素相等且前一元素尚未被使用则跳过从而保证相同值的元素只会按固定顺序被选取一次避免产生重复排列。三、完整 Go 实现继承自原文档原文档给出的核心代码如下仓库中的实现源码见 leetcode/0047.Permutations-II/47. Permutations II.gopackage leetcode import sort func permuteUnique(nums []int) [][]int { if len(nums) 0 { return [][]int{} } used, p, res : make([]bool, len(nums)), []int{}, [][]int{} sort.Ints(nums) // 这里是去重的关键逻辑 generatePermutation47(nums, 0, p, res, used) return res } func generatePermutation47(nums []int, index int, p []int, res *[][]int, used *[]bool) { if index len(nums) { temp : make([]int, len(p)) copy(temp, p) *res append(*res, temp) return } for i : 0; i len(nums); i { if !(*used)[i] { if i 0 nums[i] nums[i-1] !(*used)[i-1] { // 这里是去重的关键逻辑 continue } (*used)[i] true p append(p, nums[i]) generatePermutation47(nums, index1, p, res, used) p p[:len(p)-1] (*used)[i] false } } return }3.1 入口函数 permuteUnique 逐行解读if len(nums) 0 { return [][]int{} }空数组直接返回空结果避免后续下标访问越界used长度与nums相同的布尔数组标记每个下标是否已被当前排列路径使用p当前正在构造的排列前缀res最终结果集合类型为[][]intsort.Ints(nums)对输入排序使重复元素相邻。排序是去重能够成立的前提——只有让相同的值排在一起剪枝条件才能通过“相邻比较”识别出重复随后调用generatePermutation47开始 DFS最终返回res。3.2 递归函数 generatePermutation47 的核心逻辑终止条件index len(nums)时说明已经选满了 n 个元素。此时需要把p拷贝一份copy(temp, p)再追加到res因为p在后续回溯中会被复用和修改不能直接引用遍历选取每一层从0到len(nums)-1尝试所有下标!(*used)[i]保证同一路径内不重复选取同一个下标去重剪枝最关键的一行if i 0 nums[i] nums[i-1] !(*used)[i-1] { continue }i 0防止对第一个元素访问nums[i-1]越界nums[i] nums[i-1]当前元素与前一个元素值相同说明遇到了重复元素!(*used)[i-1]前一个相同元素尚未被使用。结合“排序后相同元素相邻”的前提这表示在当前层之前相同值的元素还没有被选取过。此时若再选取nums[i]就会产生与先选nums[i-1]完全相同的排列分支因此直接剪枝跳过。这条条件的本质是规定相同值的多个元素必须按下标顺序依次被选取先取前一个才允许取后一个从而把重复元素产生的对称分支合并为一条从根源上杜绝重复排列而不需要最后再对结果做一次全局去重。回溯选取元素后递归进入下一层递归返回后执行p p[:len(p)-1]撤销选取并把(*used)[i] false释放下标恢复现场以便尝试其他分支。四、与第 46 题Permutations的对比原文档明确指出本题是第 46 题的加强版。对比仓库中两份实现可以直观看到差异第 46 题的 DFS 循环体leetcode/0046.Permutations/46. Permutations.go只有if !(*used)[i] { (*used)[i] true p append(p, nums[i]) generatePermutation(nums, index1, p, res, used) p p[:len(p)-1] (*used)[i] false }即无重复前提下只需保证「每个下标只用一次」即可枚举出全部 n! 个排列。第 47 题在同样的框架上增加两处去重设施入口处sort.Ints(nums)循环体内的相邻重复剪枝判断if i 0 nums[i] nums[i-1] !(*used)[i-1] { continue }。其余结构used 标记、p 前缀、递归终止拷贝、回溯复位完全一致。因此从源码结构可以推断掌握第 46 题的 DFS 框架后只需理解「排序 相邻重复剪枝」这一条规则就能自然迁移到本题。五、仓库测试用例验证去重正确性仓库为该题提供了完整的表驱动测试见 leetcode/0047.Permutations-II/47. Permutations II_test.go共覆盖 4 组输入输入期望输出覆盖意图[1, 1, 2][[1 1 2] [1 2 1] [2 1 1]]题目标准示例两个重复元素1[1, 2, 2][[1 2 2] [2 2 1] [2 1 2]]重复元素位于尾部验证剪枝在不同位置的正确性[2, 2, 2][[2 2 2]]全部元素相同全排列退化为仅 1 个结果[][]空数组边界验证入口处的空值保护这四组用例分别覆盖了「重复在头部」「重复在尾部」「全重复」「空输入」四种典型场景可以有效验证去重剪枝逻辑的正确性与边界安全。测试函数通过question47结构体组织参数与期望答案循环打印输入输出fmt.Printf(【input】:%v 【output】:%v\n, p, permuteUnique(p.s))测试运行命令与仓库 gotest.sh 中使用的命令一致该脚本同时以 atomic 模式生成覆盖率文件go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只运行本目录下的测试go test ./leetcode/0047.Permutations-II/...六、复杂度与空间分析以仓库实现为准进行推断时间复杂度最坏情况下所有元素互不相同退化为第 46 题全排列数量为 n!每个排列需要 O(n) 时间拷贝入结果因此为O(n × n!)。当存在大量重复元素时剪枝会显著减少实际枚举的分支数例如[2,2,2]只产生 1 个结果而非 6 个分支。空间复杂度递归深度为 O(n)调用栈p与used均为 O(n)结果集本身需要存储 O(n × n!) 的空间该部分不计入辅助空间时可视为 O(n)。七、小结与延伸本题的完整脉络可以概括为一条主线排序使重复相邻 → DFS 按层选取 → 相邻重复且前驱未选则剪枝 → 回溯复位。这条「排序 used 前驱剪枝」的组合拳是含重复元素组合类/排列类问题如子集 II、组合总和 II 等的通用套路值得反复推敲。相关的仓库资料索引题目说明文档中文版leetcode/0047.Permutations-II/README.md英文版题目文档website/content.en/ChapterFour/0001~0099/0047.Permutations-II.md实现源码leetcode/0047.Permutations-II/47. Permutations II.go测试用例leetcode/0047.Permutations-II/47. Permutations II_test.go无重复版本对照实现leetcode/0046.Permutations/46. Permutations.go【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考