LeetCode 90 子集 IISubsets II全解法详解含重复元素数组的子集枚举与去重策略【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 LeetCode 90「子集 II」Subsets II为核心讲解如何在包含重复元素的整数数组上枚举所有互不相同的子集幂集。文中完整覆盖暴力去重、两种回溯Backtracking剪枝与迭代扩展四条解题路线并逐一给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的实现。读者读完将掌握排序 剪枝这一处理重复元素的通用范式可直接迁移到组合求和、排列去重等同类回溯问题中。前置知识在动手实现前建议先熟练掌握以下三项基础能力它们是本问题所有解法共同的地基回溯Backtracking通过递归包含/排除的决策来穷举所有子集的核心技巧也是本仓库中 组合问题combination-target-sum、全排列permutations 等题目的公共基础排序Sorting本问题的关键预处理步骤——只有先排序重复元素才会相邻后续的跳过逻辑才有意义递归Recursion理解如何增量式地构建解以及在回溯时撤销上一步选择。如果你希望先从无重复元素的版本开始热身可以对照阅读同仓库的 subsets.mdLeetCode 78它只包含包含/排除的二元决策树而本问题在它的基础上额外引入了去重这一层复杂度。问题回顾给定一个可能包含重复元素的整数数组nums返回所有可能的子集幂集且解集不能包含重复的子集。例如输入nums [1,2,2]输出应为[[], [1], [1,2], [1,2,2], [2], [2,2]]注意[2]只能出现一次——虽然数组里有两个2但子集[2]是同一个集合。这正是本题与 LeetCode 78无重复元素版的本质差异重复元素导致同一子集可能被多次生成必须去重。1. 暴力法全量生成 哈希集合去重核心思路这是最容易想到、也最粗暴的解法先不管重复把所有子集都生成出来最后再统一去重。对每个索引做二元选择包含当前数字或跳过当前数字由于存在重复元素许多生成的子集看起来一样因此需要去重先对数组排序让重复元素相邻将每个子集以元组tuple形式存入集合set——集合天然去重且元组可哈希Python 的 list 不可哈希无法直接入 set。最后把 set 中的元组转回 list 列表即可。算法步骤排序输入数组定义递归函数处理完全部数字 → 将当前子集转成 tuple加入 set否则包含当前数字 → 递归排除当前数字 → 递归穷举结束后把 set 中的元组转换为列表返回唯一子集列表。代码实现以下为 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的实现class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: res set() def backtrack(i, subset): if i len(nums): res.add(tuple(subset)) return subset.append(nums[i]) backtrack(i 1, subset) subset.pop() backtrack(i 1, subset) nums.sort() backtrack(0, []) return [list(s) for s in res]public class Solution { SetListInteger res new HashSet(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(nums, 0, new ArrayList()); return new ArrayList(res); } private void backtrack(int[] nums, int i, ListInteger subset) { if (i nums.length) { res.add(new ArrayList(subset)); return; } subset.add(nums[i]); backtrack(nums, i 1, subset); subset.remove(subset.size() - 1); backtrack(nums, i 1, subset); } }class Solution { setvectorint res; public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); backtrack(nums, 0, {}); return vectorvectorint(res.begin(), res.end()); } void backtrack(vectorint nums, int i, vectorint subset) { if (i nums.size()) { res.insert(subset); return; } subset.push_back(nums[i]); backtrack(nums, i 1, subset); subset.pop_back(); backtrack(nums, i 1, subset); } };class Solution { constructor() { this.res new Set(); } subsetsWithDup(nums) { nums.sort((a, b) a - b); this.backtrack(nums, 0, []); return Array.from(this.res).map((subset) JSON.parse(subset)); } backtrack(nums, i, subset) { if (i nums.length) { this.res.add(JSON.stringify(subset)); return; } subset.push(nums[i]); this.backtrack(nums, i 1, subset); subset.pop(); this.backtrack(nums, i 1, subset); } }public class Solution { HashSetstring res new HashSetstring(); public ListListint SubsetsWithDup(int[] nums) { Array.Sort(nums); Backtrack(nums, 0, new Listint()); ListListint result new ListListint(); result.Add(new Listint()); res.Remove(); foreach (string str in res) { Listint subset new Listint(); string[] arr str.Split(,); foreach (string num in arr) { subset.Add(int.Parse(num)); } result.Add(subset); } return result; } private void Backtrack(int[] nums, int i, Listint subset) { if (i nums.Length) { res.Add(string.Join(,, subset)); return; } subset.Add(nums[i]); Backtrack(nums, i 1, subset); subset.RemoveAt(subset.Count - 1); Backtrack(nums, i 1, subset); } }func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) res : make(map[string][]int) var backtrack func(int, []int) backtrack func(i int, subset []int) { if i len(nums) { key : fmt.Sprint(subset) res[key] append([]int{}, subset...) return } subset append(subset, nums[i]) backtrack(i1, subset) subset subset[:len(subset)-1] backtrack(i1, subset) } backtrack(0, []int{}) var result [][]int for _, v : range res { result append(result, v) } return result }class Solution { fun subsetsWithDup(nums: IntArray): ListListInt { nums.sort() val res HashSetListInt() fun backtrack(i: Int, subset: MutableListInt) { if (i nums.size) { res.add(ArrayList(subset)) return } subset.add(nums[i]) backtrack(i 1, subset) subset.removeAt(subset.size - 1) backtrack(i 1, subset) } backtrack(0, mutableListOf()) return res.toList() } }class Solution { func subsetsWithDup(_ nums: [Int]) - [[Int]] { var res Set[Int]() var subset [Int]() let nums nums.sorted() func backtrack(_ i: Int) { if i nums.count { res.insert(subset) return } subset.append(nums[i]) backtrack(i 1) subset.removeLast() backtrack(i 1) } backtrack(0) return Array(res) } }impl Solution { pub fn subsets_with_dup(nums: Veci32) - VecVeci32 { let mut nums nums; nums.sort(); let mut res: HashSetVeci32 HashSet::new(); fn backtrack(nums: [i32], i: usize, subset: mut Veci32, res: mut HashSetVeci32) { if i nums.len() { res.insert(subset.clone()); return; } subset.push(nums[i]); backtrack(nums, i 1, subset, res); subset.pop(); backtrack(nums, i 1, subset, res); } backtrack(nums, 0, mut vec![], mut res); res.into_iter().collect() } }实现细节JavaScript 中数组无法直接作为Set元素因此用JSON.stringify序列化后去重C# 用逗号拼接字符串存入HashSetGo 则用fmt.Sprint生成 map 键。各语言都在用自己可哈希的等价物完成同一件事。时间与空间复杂度时间复杂度$O(n \cdot 2^n)$ —— 生成 $2^n$ 个子集每个拷贝需要 $O(n)$空间复杂度$O(2^n)$ —— 哈希集合中最多存放 $2^n$ 个唯一子集。暴力法正确但不够优雅它生成了大量注定要被丢弃的重复子集且额外的哈希结构带来了 $O(2^n)$ 的存储开销。本仓库 hints/subsets-ii.md 的 Hint 1 也直接点明哈希集合方案需要 $O(2^n)$ 额外空间提示我们寻找更优做法——也就是下面两种回溯剪枝方案。2. 回溯法 I选/不选决策 跳过重复值核心思路我们希望得到所有子集但数组可能含重复元素。如果盲目生成全部子集必然产生重复结果因此必须做到在同一决策层上同一个值只被取用一次。关键思想在每个索引i处做两个选择包含nums[i]排除nums[i]但排除分支存在隐患如果下一个数字相同nums[i] nums[i1]那么现在跳过它、以后再处理与现在不跳过会产出相同的子集。因此探索完排除分支后一次性跳过所有重复值避免重复子集同样需要先排序让重复值连续排列、便于跳跃。算法步骤排序输入数组定义递归函数backtrack(i, subset)若i到达末尾 → 将subset的副本加入结果否则包含nums[i]→ 递归i1排除nums[i]先将i向前移动跳过所有与nums[i]相同的值再从下一个不重复的索引递归返回结果列表。代码实现class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: res [] nums.sort() def backtrack(i, subset): if i len(nums): res.append(subset[::]) return subset.append(nums[i]) backtrack(i 1, subset) subset.pop() while i 1 len(nums) and nums[i] nums[i 1]: i 1 backtrack(i 1, subset) backtrack(0, []) return respublic class Solution { ListListInteger res new ArrayList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(0, new ArrayList(), nums); return res; } private void backtrack(int i, ListInteger subset, int[] nums) { if (i nums.length) { res.add(new ArrayList(subset)); return; } subset.add(nums[i]); backtrack(i 1, subset, nums); subset.remove(subset.size() - 1); while (i 1 nums.length nums[i] nums[i 1]) { i; } backtrack(i 1, subset, nums); } }class Solution { vectorvectorint res; public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); backtrack(0, {}, nums); return res; } void backtrack(int i, vectorint subset, vectorint nums) { if (i nums.size()) { res.push_back(subset); return; } subset.push_back(nums[i]); backtrack(i 1, subset, nums); subset.pop_back(); while (i 1 nums.size() nums[i] nums[i 1]) { i; } backtrack(i 1, subset, nums); } };class Solution { subsetsWithDup(nums) { let res []; nums.sort((a, b) a - b); const backtrack (i, subset) { if (i nums.length) { res.push([...subset]); return; } subset.push(nums[i]); backtrack(i 1, subset); subset.pop(); while (i 1 nums.length nums[i] nums[i 1]) { i; } backtrack(i 1, subset); }; backtrack(0, []); return res; } }public class Solution { ListListint res new ListListint(); public ListListint SubsetsWithDup(int[] nums) { Array.Sort(nums); Backtrack(0, new Listint(), nums); return res; } private void Backtrack(int i, Listint subset, int[] nums) { if (i nums.Length) { res.Add(new Listint(subset)); return; } subset.Add(nums[i]); Backtrack(i 1, subset, nums); subset.RemoveAt(subset.Count - 1); while (i 1 nums.Length nums[i] nums[i 1]) { i; } Backtrack(i 1, subset, nums); } }func subsetsWithDup(nums []int) [][]int { var res [][]int sort.Ints(nums) var backtrack func(int, []int) backtrack func(i int, subset []int) { if i len(nums) { res append(res, append([]int{}, subset...)) return } subset append(subset, nums[i]) backtrack(i1, subset) subset subset[:len(subset)-1] for i1 len(nums) nums[i] nums[i1] { i } backtrack(i1, subset) } backtrack(0, []int{}) return res }class Solution { fun subsetsWithDup(nums: IntArray): ListListInt { val res mutableListOfListInt() nums.sort() fun backtrack(i: Int, subset: MutableListInt) { if (i nums.size) { res.add(ArrayList(subset)) return } subset.add(nums[i]) backtrack(i 1, subset) subset.removeAt(subset.size - 1) var j i while (j 1 nums.size nums[j] nums[j 1]) { j } backtrack(j 1, subset) } backtrack(0, mutableListOf()) return res } }class Solution { func subsetsWithDup(_ nums: [Int]) - [[Int]] { var res [[Int]]() var subset [Int]() let nums nums.sorted() func backtrack(_ i: Int) { if i nums.count { res.append(subset) return } subset.append(nums[i]) backtrack(i 1) subset.removeLast() var j i while j 1 nums.count nums[j] nums[j 1] { j 1 } backtrack(j 1) } backtrack(0) return res } }impl Solution { pub fn subsets_with_dup(nums: Veci32) - VecVeci32 { let mut nums nums; nums.sort(); let mut res Vec::new(); fn backtrack(nums: [i32], i: usize, subset: mut Veci32, res: mut VecVeci32) { if i nums.len() { res.push(subset.clone()); return; } subset.push(nums[i]); backtrack(nums, i 1, subset, res); subset.pop(); let mut j i; while j 1 nums.len() nums[j] nums[j 1] { j 1; } backtrack(nums, j 1, subset, res); } backtrack(nums, 0, mut vec![], mut res); res } }这一版正是本仓库 python/0090-subsets-ii.py 与 rust/0090-subsets-ii.rs 中收录的官方实现注释清晰标出包含nums[i]的所有子集与不包含nums[i]的所有子集两大分支while循环即去重核心。对照 hints/subsets-ii.md 的 Hint 2、Hint 3 可以发现提示所引导的正是这条排序 相同值跳过的路线。时间与空间复杂度时间复杂度$O(n \cdot 2^n)$空间复杂度额外空间 $O(n)$递归栈深度结果列表本身占用 $O(2^n)$。相比暴力法它不再需要哈希集合额外空间从 $O(2^n)$ 降到 $O(n)$同时避免了生成大量废弃的重复子集。3. 回溯法 II逐步选下一个元素 j i剪枝核心思路不再做选/不选的二元决策而是每一层从当前索引往后选择一个下一个元素但同一层中每个唯一值只选一次从根源上杜绝重复子集。关键思想排序使相同数字相邻在每个递归层内用循环让j从当前索引i遍历到数组末尾若nums[j] nums[j-1]且j i则跳过。该条件保证在本层决策中重复值只允许第一次出现时被选中从而避免生成以相同前缀开头的重复子集每次进入backtrack时先把当前subset推入res这意味着空集也会在第一层被记录。这一方案保证每个子集恰好生成一次、所有合法子集全部覆盖、无需任何集合类辅助数据结构。算法步骤排序输入数组聚拢重复元素定义递归函数backtrack(i, subset)将当前子集加入结果对j从i到末尾遍历若j i且nums[j] nums[j-1]跳过重复选择将nums[j]加入子集递归调用backtrack(j 1, subset)移除该元素回溯撤销以backtrack(0, [])启动返回结果。代码实现class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] def backtrack(i, subset): res.append(subset[::]) for j in range(i, len(nums)): if j i and nums[j] nums[j - 1]: continue subset.append(nums[j]) backtrack(j 1, subset) subset.pop() backtrack(0, []) return respublic class Solution { ListListInteger res new ArrayList(); public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(0, new ArrayList(), nums); return res; } private void backtrack(int i, ListInteger subset, int[] nums) { res.add(new ArrayList(subset)); for (int j i; j nums.length; j) { if (j i nums[j] nums[j - 1]) { continue; } subset.add(nums[j]); backtrack(j 1, subset, nums); subset.remove(subset.size() - 1); } } }class Solution { public: vectorvectorint res; vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); backtrack(0, {}, nums); return res; } void backtrack(int i, vectorint subset, vectorint nums) { res.push_back(subset); for (int j i; j nums.size(); j) { if (j i nums[j] nums[j - 1]) { continue; } subset.push_back(nums[j]); backtrack(j 1, subset, nums); subset.pop_back(); } } };class Solution { constructor() { this.res []; } subsetsWithDup(nums) { nums.sort((a, b) a - b); this.backtrack(0, [], nums); return this.res; } backtrack(i, subset, nums) { this.res.push([...subset]); for (let j i; j nums.length; j) { if (j i nums[j] nums[j - 1]) { continue; } subset.push(nums[j]); this.backtrack(j 1, subset, nums); subset.pop(); } } }public class Solution { private ListListint res new ListListint(); public ListListint SubsetsWithDup(int[] nums) { Array.Sort(nums); Backtrack(0, new Listint(), nums); return res; } private void Backtrack(int i, Listint subset, int[] nums) { res.Add(new Listint(subset)); for (int j i; j nums.Length; j) { if (j i nums[j] nums[j - 1]) { continue; } subset.Add(nums[j]); Backtrack(j 1, subset, nums); subset.RemoveAt(subset.Count - 1); } } }func subsetsWithDup(nums []int) [][]int { var res [][]int sort.Ints(nums) var backtrack func(int, []int) backtrack func(i int, subset []int) { res append(res, append([]int{}, subset...)) for j : i; j len(nums); j { if j i nums[j] nums[j-1] { continue } subset append(subset, nums[j]) backtrack(j1, subset) subset subset[:len(subset)-1] } } backtrack(0, []int{}) return res }class Solution { fun subsetsWithDup(nums: IntArray): ListListInt { val res mutableListOfListInt() nums.sort() fun backtrack(i: Int, subset: MutableListInt) { res.add(ArrayList(subset)) for (j in i until nums.size) { if (j i nums[j] nums[j - 1]) { continue } subset.add(nums[j]) backtrack(j 1, subset) subset.removeAt(subset.size - 1) } } backtrack(0, mutableListOf()) return res } }class Solution { func subsetsWithDup(_ nums: [Int]) - [[Int]] { var res [[Int]]() var subset [Int]() let nums nums.sorted() func backtrack(_ i: Int) { res.append(subset) for j in i..nums.count { if j i nums[j] nums[j - 1] { continue } subset.append(nums[j]) backtrack(j 1) subset.removeLast() } } backtrack(0) return res } }impl Solution { pub fn subsets_with_dup(nums: Veci32) - VecVeci32 { let mut nums nums; nums.sort(); let mut res Vec::new(); fn backtrack(nums: [i32], i: usize, subset: mut Veci32, res: mut VecVeci32) { res.push(subset.clone()); for j in i..nums.len() { if j i nums[j] nums[j - 1] { continue; } subset.push(nums[j]); backtrack(nums, j 1, subset, res); subset.pop(); } } backtrack(nums, 0, mut vec![], mut res); res } }这一版是当前仓库中最主流的提交形态本仓库 java/0090-subsets-ii.javasubSet方法、cpp/0090-subsets-ii.cppdfs方法、go/0090-subsets-ii.go 以及 c/0090-subsets-ii.c 均采用此结构。Go 实现中特意注释了//not backtrack(idx 1)!!提醒递归必须从i 1继续而不是idx 1否则会错误地重复组合元素C 实现则用qsort排序配合手动管理的内存数组完成同样的遍历。时间与空间复杂度时间复杂度$O(n \cdot 2^n)$空间复杂度额外空间 $O(n)$递归栈 临时子集结果列表占用 $O(2^n)$。两种回溯法的对比回溯法 I 通过排除分支时跳过重复去重回溯法 II 通过每层只选每个唯一值一次去重前者代码短、语义贴近选/不选直觉后者在需要按顺序枚举前缀组合的场景如组合求和中复用度更高。两者时间复杂度相同空间上均只需 $O(n)$ 辅助空间。4. 迭代法按轮次扩展 记录上一轮边界核心思路迭代法不依赖递归而是逐元素地扩展已有子集。常规做法是每来一个新数字就把它追加到所有已存在的子集后面。但重复元素会导致重复子集因此必须限制重复数字只能与上一轮新增的子集结合不能与更早的全部子集结合。关键思想排序让重复元素相邻维护两个索引idx本轮生成新子集的起点prev_idx上一轮结束时的结果列表大小即旧子集的边界若当前数字不是重复→ 从开头开始扩展idx 0若当前数字是重复→ 只与上一轮创建的子集结合idx prev_idx从而避免重复子集。示例输入[1,2,2]第一个2扩展所有已有子集第二个2只扩展第一个2处理时新增的那些子集 → 不会产生重复。算法步骤排序nums使重复元素相邻初始化res [[]]对每个索引i若nums[i]与nums[i-1]相同 →idx取上一轮边界prev_idx否则 →idx 0记录prev_idx len(res)本轮旧子集边界对j从idx到prev_idx - 1复制res[j]并追加nums[i]形成新子集加入res返回res。代码实现class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [[]] prev_Idx idx 0 for i in range(len(nums)): idx prev_idx if i 1 and nums[i] nums[i - 1] else 0 prev_idx len(res) for j in range(idx, prev_idx): tmp res[j].copy() tmp.append(nums[i]) res.append(tmp) return respublic class Solution { public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); res.add(new ArrayList()); int prevIdx 0; int idx 0; for (int i 0; i nums.length; i) { idx (i 1 nums[i] nums[i - 1]) ? prevIdx : 0; prevIdx res.size(); for (int j idx; j prevIdx; j) { ListInteger tmp new ArrayList(res.get(j)); tmp.add(nums[i]); res.add(tmp); } } return res; } }class Solution { public: vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res {{}}; int prevIdx 0; int idx 0; for (int i 0; i nums.size(); i) { idx (i 1 nums[i] nums[i - 1]) ? prevIdx : 0; prevIdx res.size(); for (int j idx; j prevIdx; j) { std::vectorint tmp res[j]; tmp.push_back(nums[i]); res.push_back(tmp); } } return res; } };class Solution { subsetsWithDup(nums) { nums.sort((a, b) a - b); const res [[]]; let prevIdx 0; let idx 0; for (let i 0; i nums.length; i) { idx i 1 nums[i] nums[i - 1] ? prevIdx : 0; prevIdx res.length; for (let j idx; j prevIdx; j) { const tmp [...res[j]]; tmp.push(nums[i]); res.push(tmp); } } return res; } }public class Solution { public ListListint SubsetsWithDup(int[] nums) { Array.Sort(nums); var res new ListListint { new Listint() }; int prevIdx 0; int idx 0; for (int i 0; i nums.Length; i) { idx (i 1 nums[i] nums[i - 1]) ? prevIdx : 0; prevIdx res.Count; for (int j idx; j prevIdx; j) { var tmp new Listint(res[j]); tmp.Add(nums[i]); res.Add(tmp); } } return res; } }func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) res : [][]int{{}} prevIdx, idx : 0, 0 for i : 0; i len(nums); i { if i 0 nums[i] nums[i-1] { idx prevIdx } else { idx 0 } prevIdx len(res) for j : idx; j prevIdx; j { tmp : append([]int{}, res[j]...) tmp append(tmp, nums[i]) res append(res, tmp) } } return res }class Solution { fun subsetsWithDup(nums: IntArray): ListListInt { nums.sort() val res mutableListOf(listOfInt()) var prevIdx 0 var idx 0 for (i in nums.indices) { idx if (i 0 nums[i] nums[i - 1]) prevIdx else 0 prevIdx res.size for (j in idx until prevIdx) { val tmp ArrayList(res[j]) tmp.add(nums[i]) res.add(tmp) } } return res } }class Solution { func subsetsWithDup(_ nums: [Int]) - [[Int]] { let nums nums.sorted() var res: [[Int]] [[]] var prevIdx 0 var idx 0 for i in 0..nums.count { idx (i 1 nums[i] nums[i - 1]) ? prevIdx : 0 prevIdx res.count for j in idx..prevIdx { var temp res[j] temp.append(nums[i]) res.append(temp) } } return res } }impl Solution { pub fn subsets_with_dup(nums: Veci32) - VecVeci32 { let mut nums nums; nums.sort(); let mut res: VecVeci32 vec![vec![]]; let mut prev_idx 0usize; for i in 0..nums.len() { let idx if i 1 nums[i] nums[i - 1] { prev_idx } else { 0 }; prev_idx res.len(); for j in idx..prev_idx { let mut tmp res[j].clone(); tmp.push(nums[i]); res.push(tmp); } } res } }本仓库 javascript/0090-subsets-ii.js 中的bfs函数正是该迭代思路的另一种表达用levels记录上一轮边界isPrevDuplicate决定本轮起点通过逐层扩展生成全部子集。时间与空间复杂度时间复杂度$O(n \cdot 2^n)$空间复杂度额外空间 $O(1)$只有两个游标变量结果列表占用 $O(2^n)$。迭代法在四种方案中辅助空间最省且没有递归栈开销非常适合在意栈深度或希望显式控制扩展过程的场景。常见陷阱忘记先排序排序是整道题的命门它把重复元素聚拢到一起后续的跳过逻辑才可能成立。若不排序重复元素散落在数组各处无法被可靠检测和跳过最终必然产出重复子集。四种解法无一例外都要求第一步nums.sort()。去重条件写错回溯法 II 的去重条件必须写成j i nums[j] nums[j-1]而不能是j 0或j i写成j 0会跳过每个递归层中重复值的第一次出现导致合法子集如[1,2,2]中的[2,2]被误删正确语义只在当前决策层内跳过重复值的后续出现——j i保证了i位置的元素本层的第一个候选总是被允许选中。错误地修改子集引用向结果中添加子集时必须拷贝当前子集Python 用subset[:]/subset.copy()Java 用new ArrayList(subset)Go 用append([]int{}, subset...)Rust 用subset.clone()。若直接把引用加入结果回溯过程中的push/pop会持续改写同一块内存最终结果列表中的所有条目都会指向同一个被改得面目全非的列表。递归起点传错回溯法 II 中递归调用必须传j 1当前选中元素的下一个索引而不是i 1或idx 1——正如本仓库 go/0090-subsets-ii.go 中以注释醒目标注的那样。传错起点会导致元素被重复组合产出错误子集。总结四种解法从正确性优先到效率优先层层递进解法核心机制额外空间适用评价暴力法全量生成 哈希集合去重$O(2^n)$思路直观适合快速验证正确性回溯法 I选/不选决策排除分支跳过重复$O(n)$语义清晰贴近决策树直觉回溯法 II每层循环选元素j i剪枝$O(n)$工程上最常用可迁移到组合类题目迭代法按轮扩展仅与上一轮新增子集结合$O(1)$辅助空间最小无递归栈所有方案的时间复杂度均为 $O(n \cdot 2^n)$输出本身就有 $2^n$ 个集合已是最优下界。无论选择哪条路线排序 在决策层内跳过重复值都是整个去重范式的灵魂——掌握它你就掌握了含重复元素数组枚举类问题的通用解法。仓库中的完整实现见 python/0090-subsets-ii.py、c/0090-subsets-ii.c、cpp/0090-subsets-ii.cpp、java/0090-subsets-ii.java、javascript/0090-subsets-ii.js、go/0090-subsets-ii.go、rust/0090-subsets-ii.rs 等文件可直接对照阅读。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考