什么是回溯（Backtracking）？为什么要使用它？

What is backtracking, and why do we use it?

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: hard

分类: algorithms

标签: backtracking, recursion, search

参考答案摘要

TL;DR 回溯是一种递归搜索策略，通过逐步构建解并在不满足条件时撤销选择，常用于求可行解、最优解或枚举所有解的问题。 回溯是一种解决问题的算法策略。它通过递归调用，随着时间推进不断尝试扩大选择以找到解。回溯也被视为对暴力破解的升级，我们可以用它编写算法解决一些特定类型的问题。 回溯常用于以下问题类型： 判定问题（Decision problem） ：用于找到问题的可行解。 优化问题（Optimi...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。