面试题库 › 算法 / 大模型 › 划分为 k 个相等的子集(LeetCode 698)

划分为 k 个相等的子集(LeetCode 698)

难度 ★★★在 2 场真实面经中被问到 方向:算法 / 大模型考点:贪心与回溯

哪些公司问过

华为1阿里健康1

常见岗位:大模型算法、C/C++ 软件开发

答案要点

  1. 预判:sum % k ≠ 0 或最大元素 > target 时直接返回 false
  2. 桶回溯:数字降序排列,依次为每个数尝试放入 k 个桶
  3. 剪枝:超出 target 跳过;与前一个桶和相同跳过;放入空桶失败则直接返回
  4. 状压 DP:dp[mask] 记录已选集合对应的当前桶余量,O(n·2^n) 时间
  5. 回溯最坏 O(k^n)、递归栈 O(n);状压 DP 空间 O(2^n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题