回溯算法 Backtracking

視頻一：回溯算法套路①子集型回溯【基礎(chǔ)算法精講 14】

視頻二：回溯算法套路②組合型回溯+剪枝【基礎(chǔ)算法精講 15】

視頻三：回溯算法套路③排列型回溯+N皇后【基礎(chǔ)算法精講 16】

回溯三問：

????1. 當(dāng)前操作？? 2. 子問題？? ?3. 下一個(gè)子問題？

子集型回溯

????套路一：本質(zhì)上每個(gè)元素都可以?選/不選

????套路二：為避免重復(fù)，可人為規(guī)定選取順序（按下標(biāo)增大的方向，即選了 a[i] 后，之后的選取只能在 [i+1, n) 中選?。?。即所謂的【答案視角】指的就是在 [i, n) 中找?“下一個(gè)元素選啥”，然后根據(jù)該選擇繼續(xù)遞歸

????這題主要是兩種模版的得出，其中第二種我覺得比較難想，需要再適應(yīng)一下。

組合型回溯

????注意到組合型回溯就是長度固定的子集型回溯模版二的某一層答案，所以可以進(jìn)行額外優(yōu)化，即剪枝

排列型回溯

????運(yùn)用之妙，存乎一心。靈神真是讓人高山仰止啊。