全排列回溯算法的时间复杂度和空间复杂度是多少?
哪些公司问过
答案要点
- 共 n! 个排列,每个复制 O(n),时间 O(n×n!)
- 递归树内部节点总数约 e×n!,每节点循环 n 次,量级一致
- 不计输出空间为 O(n):递归深度 n,加 path 和 visited
- 计入结果集则空间 O(n×n!)
- 交换法省去 visited;有重复元素先排序再同层剪枝
易错点
- 只说 O(n!),漏掉每个排列复制的 O(n)
- 空间复杂度不说明是否包含输出
- 以为交换法能把递归栈空间也省掉
面试官常见追问
- 全排列 II(含重复元素)怎么去重?
- next_permutation 是怎么实现的?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。