# 回溯算法 > 原文： [https://www.programiz.com/dsa/backtracking-algorithm](https://www.programiz.com/dsa/backtracking-algorithm) #### 在本教程中，您將學習什么是回溯算法。 此外，您還將找到回溯方法的示例。 回溯算法是一種解決問題的算法，它使用**暴力方法**來查找所需的輸出。 暴力方法會嘗試所有可能的解決方案，然后選擇所需/最佳解決方案。 術語“回溯”表示如果當前解決方案不合適，則回溯并嘗試其他解決方案。 因此，在此方法中使用了遞歸。 此方法用于解決具有多種解決方案的問題。 如果需要最佳解決方案，則必須進行[動態規劃](/dsa/dynamic-programming)。 * * * ## 狀態空間樹 空間狀態樹是表示問題的所有可能狀態（解決方案或非解決方案）的樹，該問題從根作為初始狀態到葉作為終端狀態。  狀態空間樹 * * * ## 回溯算法 ``` Backtrack(x) if x is not a solution return false if x is a new solution add to list of solutions backtrack(expand x) ``` * * * ## 回溯方法示例 問題：您想找到所有可能的方式在 3 個長凳上安排 2 個男孩和 1 個女孩。 約束：女孩不應該坐在中間的長凳上。 解決方案：共有`3! = 6`種可能性。 我們將嘗試所有可能性并獲得可能的解決方案。 我們遞歸地嘗試所有可能性。 所有可能性是：  所有可能性 以下[狀態空間樹](http://None)顯示了可能的解決方案。  狀態樹與所有解決方案 * * * ## 回溯算法應用 1. 查找圖中存在的所有[哈密頓路徑](https://en.wikipedia.org/wiki/Hamiltonian_path_problem)。 2. [解決 N 皇后問題](https://en.wikipedia.org/wiki/Eight_queens_puzzle)。 3. [解決迷宮問題](https://en.wikipedia.org/wiki/Maze_solving_algorithm)。 4. [騎士的旅行問題](https://en.wikipedia.org/wiki/Knight%27s_tour)。