把数组分成和相等的若干组,求最小组内和
哪些公司问过
答案要点
- 组内和最小等价于组数最多,枚举k从大到小
- 候选组和必须整除总和,且不小于最大元素
- 用回溯判断能否划分为k个和相等的子集
- 降序排序、空桶剪枝、同和桶跳过是关键剪枝
- k=1恒可行,答案最坏为总和
易错点
- 不先排序直接回溯,规模稍大就超时
- 枚举组和时没检查最大元素,做了无效搜索
- 把答案理解成最小的组数,方向搞反
面试官常见追问
- 如果要求每组必须是连续子数组呢?
- 判断能否分成k组还有别的方法吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。