划分为 k 个相等的子集(LeetCode 698)
哪些公司问过
华为1阿里健康1
答案要点
- 预判:sum % k ≠ 0 或最大元素 > target 时直接返回 false
- 桶回溯:数字降序排列,依次为每个数尝试放入 k 个桶
- 剪枝:超出 target 跳过;与前一个桶和相同跳过;放入空桶失败则直接返回
- 状压 DP:dp[mask] 记录已选集合对应的当前桶余量,O(n·2^n) 时间
- 回溯最坏 O(k^n)、递归栈 O(n);状压 DP 空间 O(2^n)
易错点
- 没有空桶剪枝,k 个空桶对称导致大量重复搜索
- 忘了先判断总和能否整除 k
- 状压时没有对 target 取模,导致跨桶的和计算错误
面试官常见追问
- 为什么要降序排序?
- 状态压缩 DP 怎么转移?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。