目錄

什么是回溯？

回溯常用來解決什么問題？

回溯的效率如何？

回溯在面試中的考察頻率

如何學(xué)好回溯？

回溯通用模板

---

什么是回溯？

回溯：你處理了之后，再進(jìn)行”撤銷“處理，”撤銷“這個動作就是回溯。

回溯常用來解決什么問題？

1.棋盤問題

2.路徑搜索問題

3.組合問題

4.排列問題

5.子集問題

回溯的效率如何？

很差很差，相當(dāng)于是暴力方法，因為它會嘗試每一個可能。

回溯在面試中的考察頻率

很高，在比試中也很高。可以用回溯解決，但是拿不到100%的分?jǐn)?shù)，可能可以拿33%或者66%。

組合問題和排列問題考的比較多。

如何學(xué)好回溯？

學(xué)好了遞歸也就學(xué)好了回溯。

一定不能陷入細(xì)節(jié)，寧愿不求甚解。先會做，再慢慢研究細(xì)節(jié)。之后就是做題，會做大量的題，大概15+。

回溯通用模板

void backtrace(參數(shù)){//結(jié)束條件：沒有路可以走了，也就是沒有元素可以選擇了；或者說找到目標(biāo)了。if(判斷是否結(jié)束){return;}for(從多個可選元素中選一個進(jìn)行回溯){//選了其中一個元素進(jìn)行處理，相當(dāng)于做標(biāo)記結(jié)果集.add(被選中的元素)backtrace(被選中的元素);//撤銷處理結(jié)果集.remove(被選中的元素)  }}