子集回溯遇到重复元素如何去重
哪些公司问过
答案要点
- 重复元素会让不同选择路径生成相同子集,需要在搜索时去重
- 先排序使相同值相邻,这是同层跳过的前提
- 同层剪枝条件:i>start 且 nums[i]==nums[i-1] 时 continue
- i==start 不跳过,保证 [2,2] 这类含多个相同值的子集仍能生成
- 时间最坏 O(n·2^n)(含拷贝),递归栈空间 O(n)
易错点
- 忘记排序就用相邻比较去重,重复元素不相邻时会失效
- 把条件写成 i>0,误删含多个相同元素的合法子集
- 用 set 对结果去重,复杂度和可读性都差,面试中常被追问优化
面试官常见追问
- 为什么条件是 i>start 而不是 i>0?
- 组合总和 II(每个数只能用一次且有重复)怎么改?
- 全排列有重复元素时去重方式一样吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。