> For the complete documentation index, see [llms.txt](https://jen-hsuan-hsieh.gitbook.io/letcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jen-hsuan-hsieh.gitbook.io/letcode/2.algorithm/2.1.backtracking-1.md).

# 2.1.Backtracking

* 1.Introduction (參考自:)
  * 中文稱作**回溯法**
  * 運用遞迴依序窮舉各個維度的數值, 製作所有可能的多維度數值, 並且**在遞迴途中避免枚舉出不正確的多維度數值**
* 2.解析
  * 當num改成字串的"ABC", Recursive tree可以表示如下(圖片來源: <http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/>)

    ![](https://github.com/jenhsuan/letcode/tree/4999a189073590294b35b42c8dfe17f9b5bebfad/assets/螢幕快照%202017-03-04%20下午9.22.30.png)
  * Backtracking的架構 (參考自:<http://programming-study-notes.blogspot.tw/2014/03/backtracking.html>)

    ```
      void backtracking()
      {
          if (填完所有空格) {
              輸出解答;
              return;
          }
          for (int i = 1; i <= 9; ++i) {
              if (i符合規則) {
                  將i填入空格;
                  backtracking(); // 遞迴下去填下個空格
                  將i從空格移除;
              }
          }
      }
    ```