題型一：排列、組合、子集相關問題

提示：這部分練習可以幫助我們熟悉「回溯算法」的一些概念和通用的解題思路。解題的步驟是：先畫圖，再編碼。去思考可以剪枝的條件，?為什么有的時候用?used?數(shù)組，有的時候設置搜索起點?begin?變量，理解狀態(tài)變量設計的想法。

• 46. 全排列（中等）
• 47. 全排列 II（中等）：思考為什么造成了重復，如何在搜索之前就判斷這一支會產(chǎn)生重復；
• 39. 組合總和（中等）
• 40. 組合總和 II（中等）
• 77. 組合（中等）
• 78. 子集（中等）
• 90. 子集 II（中等）：剪枝技巧同 47 題、39 題、40 題；
• 60. 第 k 個排列（中等）：利用了剪枝的思想，減去了大量枝葉，直接來到需要的葉子結點；
• 93. 復原 IP 地址（中等）

題型二：Flood Fill

提示：Flood 是「洪水」的意思，Flood Fill 直譯是「泛洪填充」的意思，體現(xiàn)了洪水能夠從一點開始，迅速填滿當前位置附近的地勢低的區(qū)域。類似的應用還有：PS 軟件中的「點一下把這一片區(qū)域的顏色都替換掉」，掃雷游戲「點一下打開一大片沒有雷的區(qū)域」。

下面這幾個問題，思想不難，但是初學的時候代碼很不容易寫對，并且也很難調(diào)試。我們的建議是多寫幾遍，忘記了就再寫一次，參考規(guī)范的編寫實現(xiàn)（設置?visited?數(shù)組，設置方向數(shù)組，抽取私有方法），把代碼寫對。

• 733. 圖像渲染（Flood Fill，中等）
• 200. 島嶼數(shù)量（中等）
• 130. 被圍繞的區(qū)域（中等）
• 79. 單詞搜索（中等）

說明：以上問題都不建議修改輸入數(shù)據(jù)，設置?visited?數(shù)組是標準的做法?？赡軙龅絽?shù)很多，是不是都可以寫成成員變量的問題，面試中拿不準的記得問一下面試官

題型三：字符串中的回溯問題

提示：字符串的問題的特殊之處在于，字符串的拼接生成新對象，因此在這一類問題上沒有顯示「回溯」的過程，但是如果使用?StringBuilder?拼接字符串就另當別論。
在這里把它們單獨作為一個題型，是希望朋友們能夠注意到這個非常細節(jié)的地方。

• 17. 電話號碼的字母組合（中等），題解；
• 784. 字母大小寫全排列（中等）；
• 22. 括號生成（中等）?：這道題廣度優(yōu)先遍歷也很好寫，可以通過這個問題理解一下為什么回溯算法都是深度優(yōu)先遍歷，并且都用遞歸來寫。

題型四：游戲問題

回溯算法是早期簡單的人工智能，有些教程把回溯叫做暴力搜索，但回溯沒有那么暴力，回溯是有方向地搜索。「力扣」上有一些簡單的游戲類問題，解決它們有一定的難度，大家可以嘗試一下。

• 51. N 皇后（困難）：其實就是全排列問題，注意設計清楚狀態(tài)變量，在遍歷的時候需要記住一些信息，空間換時間；
• 37. 解數(shù)獨（困難）：思路同「N 皇后問題」；
• 488. 祖瑪游戲（困難）
• 529. 掃雷游戲（困難）