Backtracking — 回溯法

photo by @priscilladupreez

回溯法是暴力破解法的一種，在列出各種可能的組合時，如果遇到不符合條件的就不再繼續向下查找，而是回到上層繼續尋找其他可能，聽起來有點抽象，可以想像有很多條岔路可以做選擇，不過已經知道有些岔路不會得到我們需要的結果，就沒有必要繼續往下找，而是折返到上個路口，繼續探索其他還沒訪問過的岔路，如同下圖所示

圖片來源:backtracking-introduction

在理解回溯法之前需要先認識permutation排列法

甚麼是permutation排列法?

是將相異物件或符號根據確定的順序重排。每個順序都稱作一個置換或排列。例如，從一到六的數字有720種排列，對應於由這些數字組成的所有不重複亦不闕漏的序列，例如”4, 5, 6, 1, 2, 3" 與1, 3, 5, 2, 4, 6。(引用自wikipedia)

假設現在有個字串ABC，試問會有幾種排列組合? 所有可能的排列組合如下圖，可以推論出公式 = 階乘

Ex.字串長度為3的話，就會有3*2*1=6種可能

用js實作

利用三個迴圈列出所有排列組合，假設字串當中任意兩個單字相同，就排除掉該組合，將程式流程畫成圖的話，會發現紫色三角形的範圍其實全部都不符合條件，(非ABC的排列組合)

因此在i=0, j=0的時候就要喊停了，回溯到i=0這一個步驟，這個中斷向下查找往回走的動作就是Backtracking

提早設定中止條件，向上回溯的程式碼如下

嘗試用雙指針的概念來解這題，利用start與i兩個指針互換位置來取得不同的排列組合，執行的步驟如下

1. start跟i都從0開始

• start=0，i=0，獲得以A為開頭的組合，ex. ABC

2. i前進一格之後與start交換位置

• start=0，i=1，獲得以B為開頭的組合，ex. BAC

3.i前進一格之後與start交換位置

• start=0，i=2，獲得以C為開頭的組合，ex. CBA

當i=2的時候意謂著i指針已經走到最後一步，這時start指針必須前進一步，i指針則退回與start指針相同的位置，依循先前的規則，start和i兩個指針所指向的字母作交換，交換完畢後 i+1

字串ABC

• start=1，i=1，兩個指針指向同個字母，交換後維持不變，依然是ABC
• start=1，i=2，兩個指針互換後，獲得ACB

字串BAC

• start=1，i=1，兩個指針指向同個字母，交換後維持不變，依然是BAC
• start=1，i=2，兩個指針互換後，獲得BCA

字串CBA

• start=1，i=1，兩個指針指向同個字母，交換後維持不變，依然是CBA
• start=1，i=2，兩個指針互換後，獲得CAB

用js實作

執行結果如下