用回溯法求和为目标值的子数组/子集
哪些公司问过
答案要点
- 先区分连续子数组和不连续的子集或组合
- 连续子数组和:前缀和 + 哈希表,O(n)
- 全正数的连续子数组可用滑动窗口
- 子集求和枚举方案才用回溯:排序、剪枝、同层去重
- 回溯为指数级,只求数量时可改用背包 DP
易错点
- 对连续子数组和使用回溯,复杂度指数级
- 有负数时仍用滑动窗口
- 前缀和哈希表忘记初始化 0 出现一次
面试官常见追问
- 前缀和为什么要初始化 0 出现一次?
- 组合总和中元素可重复使用和不可重复使用有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。