LeetCode 90 — 子集 II 是一道经典的组合问题。它要求你在有重复元素的数组中生成所有不重复的子集。很多同学在实现时会遇到两大痛点：

• 如何有效去重？ 直接枚举所有子集后再去重，效率低下且容易出现逻辑错误。
• 代码实现细节繁琐？ 特别是递归时记忆选择状态、判断前一个元素是否已被选取等细节容易被忽略。怎么说呢，

一、迭代法—— 最直观但要注意去重细节

思路概述

1️⃣ 先将 nums 排序；2️⃣ 遍历所有二进制掩码，每个掩码代表一种选取方式；3️⃣ 构造当前子集时如果出现“**前一个相同元素未被选取。而当前相同元素被选取**”的情况，就跳过此掩码，以防止产生重复子集。

完整代码

class Solution {
fun subsetsWithDup: List {
// 步骤①：先排序
nums.sort
val result = mutableListOf
val n = nums.size
// 步骤②：枚举所有掩码
for ) {
val subset = mutableListOf
var skip = false
// 步骤③：构造当前子集
for {
if )!= 0) { // 当前位为1 → 选取
// 判断是否需要跳过
if (i> 0 && nums == nums
&& )) == 0) {
skip = true
break
}
subset.add
}
}
if result.add
}
return result
}
}

复杂度分析

• 时间复杂度：\\)。枚举 \ 个掩码，每个掩码需要扫描 \ 个位置。
• 空间复杂度：\\)。临时存储单个子集所需空间；最终答案占用 \\)，与题目要求一致。
• ①忘记排序导致无法正确判断相邻相同； ②在跳过逻辑中把「未选中」写成「已选中」导致误删合法子集。

适用场景与优缺点 🟢优点 | 🟥缺点 * 简单直观，易于理解和调试 * 不需要额外递归栈开销 * 对于小规模 \ 足够快 🟥缺点 | 🟢适用范围 * 当 \ 较大时\\) 的指数增长不可避免 * 如果不熟悉位运算，对循环边界和位操作易产生 bug * 去重逻辑稍显繁琐。需要仔细维护条件判断 *

二、递归回溯法—— 更灵活但要注意剪枝技巧

思路概述 📌 对数组排序，接下来在递归过程中做两件事：

• 分支一：不选择当前元素 → 下一层继续探索。
• 分支二：选择当前元素 → 一样进入下一层。但需要保证若前一个相同元素未被选，则不能再选择当前，从而避免重复。

完整代码 🔍 建议使用 “choosePre” 标志来记录上一层是否已选择当前索引位置，从而简化判断逻辑。

class Solution {
private val res = mutableListOf
fun subsetsWithDup: List {
nums.sort
dfs,choosePrev = false)
return res
}
private fun dfs(
nums这方面，IntArray,index: Int,cur: MutableList,choosePrev: Boolean // 前一层是否已选择该位置
) {
if { // 到达末尾。将副本加入结果
res.add)
return
}
/* ---------- 不选该元素 ---------- */
dfs
/* ---------- 判断能否选该元素 ---------- */
if {
return // 前一个相同且未被选 → 跳过本分支以防重复
}
/* ---------- 执行 “选” 操作 ---------- */
cur.add
dfs
cur.removeAt
}
}

复杂度分析 ⚙️ 时间复杂度与迭代法一样是 \\)，因为仍需枚举全部合法组合；空间复杂度为 \\)，主要由递归栈和临时列表占用。按理说，

常见坑点 & 调试技巧 ❗️ 切勿在 “不选” 分支后直接返回。否则会漏掉后续“选” 分支；❗️ 如果忘记 `nums.sort` 会导致判重失效；❗️ 在 `cur.removeAt` 时一定要使用 `cur.lastIndex` 而不是硬编码索引，以免因列表大小变化而出错。老实说，

再看小结。• 对于小规模输入，两种方法都能完成起来不难；不过，• 若想提高可读性或 性，可以考虑使用回溯+剪枝策略；• 对于更大规模数据，可结合生成器或动态规划减少内存使用。但主要思想仍是“先排除重复”。🚀祝你编码愉快，