子集(LeetCode 78/90)
哪些公司问过
答案要点
- 回溯:每进入一层先把路径加入结果,包括空集
- 从起始下标遍历,递归传 i+1,回来后弹出
- 位运算:0 到 2^n-1 的二进制位表示是否选择
- 迭代:每个新元素加到已有子集上形成新子集;复杂度 O(n·2^n)
- 有重复元素:先排序,同层与前一个相同则跳过
易错点
- 只在叶子节点收集结果,漏掉中间的子集和空集
- 有重复元素时没有先排序就去重
面试官常见追问
- 子集二(有重复元素)去重的条件为什么是 i > start?
- 位运算解法有什么限制?
- 子集、组合、排列的回溯有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。