46.Permutations and 47. Permutations II

46.Permutations and 47. Permutations II

這題目要用深度搜索演算法來解答，可以參考我寫的文章

如果路徑有五個，我們需要一個一個去探訪，所以必須有一個紀錄的變數

需要熟練使用遞迴的技巧

紀錄走過的點

去紀錄我們哪個點有走過，可以使用整數的一維陣列來記錄

[0, 0, 0, 0, 0] 全部都沒走過

[0, 0, 1, 1, 0] 2, 3 被走過

遞迴五次，就可以拿到路徑的答案

不過還有一個問題需要解決

紀錄走的順序

使用堆疊（stack）, LIFO, Last In First Out） 來處理順序的問題

每遞迴一次就把當前的值加到推疊

走過必留下痕跡

哪個時候需要清掉走過的紀錄呢?

必須清掉才能再次獲得新的值，不然就會一直死循環，程式會有bug

遞迴結束的時候就把值給清掉

核心碼如下 Java範例

for (int i = 0; i < nums.length; i++) {
  if (book[i] > 0)
      continue;                  //略過已經走過的點
  book[i] = 1;                   //紀錄走過的點
  tmp.add(nums[i]);              //加入堆疊
  dfs46(ans, tmp, nums, book);   //遞迴的方法
  tmp.remove(tmp.size()-1);      //清除堆疊的最後一個
  book[i] = 0;                   //清除一維陣列的紀錄
}

遞迴停止的時間點

遞迴結束的時候需要去清除目前這個巡迴的值

這邊停止的點是

當堆疊的數量等於數組的長度的時候

這邊的例子是等於5

47題Permutations II的不同之處

做法是一樣的，所以我放在一起

就是要思考為什麼需要特別拿來做不同的題型

根據題意

46題是給不會重複的陣列 47題是給會重複的陣列

陣列重複會造成什麼後果

[1, 2, 3]
[1, 2, 3] 、 [1, 3, 2] 、 [2, 1, 3] 、 [2, 3, 1]

以上發現不果我怎麼排，只要是數組不重複，我都可以得到一組全新的數組

[1, 1, 2]
[1, 1, 2] 、 [1, 2, 1] 、 [1, 1, 2] 、 [1, 2, 1]

用一樣的排法在重複的陣列，會得到重複的解答

去除重複

紅色的數字代表紀錄有無走過，並且給一個數字方知道給值的順序

變數	值
i	陣列的索引
nums	數組
book	紀錄的一維陣列

1. 去重一要兩個值互比，所以 i > 0
2. 仔細看上面的圖，nums[i-1] 等於 nums[i] 並且 book[i-1] 一定是1，因為這樣可以 保證執行的順序，只要保證是從前往後找，就不會有重複的問題
3. [1, 2, 1] 這種數組就會有問題，因為我們的算法是 i 跟 i-1 的比較，本來以為算完了 但後面其實還有，不過只要排序數組就可以解結問題了，變成[1, 1, 2]