回溯法

參考 - 劍指Offer

回溯法可以看成蠻力法的升級版,它從解決問題每一步的所有可能選項里系統地選擇出一個可行的解決方案.

回溯法解決的問題的特性:

• 可以形象地用樹狀結構表示:

  • 節點: 算法中的每一個步驟
  • 節點之間的連接線: 每個步驟中的選項,通過每一天連接線,可以到達下一個子步驟
  • 葉子節點: 代表一個步驟的最終狀態

• 如果在葉節點的狀態滿足需求,那么我們找到了一個可行的解決方案

• 如果在葉節點的狀態不滿足約束條件,那么只好回溯到它的上一個節點再嘗試其他的選項。如果上一個節點所有可能的選項都已經試過,并且不能達到滿足約束條件的終結狀態,則再次回溯到上一個節點.如果所有節點的所有選項都已經嘗試過仍然不能達到滿足約束條件的終結狀態,該問題無解

栗子 - 數組總和

題目參考 - 39.數組總和

算法思路:

• 變量:
  • 使用len緩存當前數組的長度
  • 使用path緩存當前的路徑
  • 使用res緩存要返回的結果
• 處理:
  • 為了方便后續的剪枝操作,需先對數組進行排序
• 使用深度優先算法,傳入3個參數: resides(離目標還差多少), path, begin(從哪一個開始添加)
  • 每次進入時,判斷一下,resides是否小于0:
    • 是: return
    • 否: 不做處理
  • 之后判斷resides是否等于0
    • 是: 證明找到一個條符合要求的路徑,將path推入res中(此處需特別注意,數組是JS中的引用類型.在后文中會回溯,最終的path是一個空數組. 如果直接將path推入res.其實是將path的內存地址推入res.最終會根據地址尋找到空數組.因此此處推入的是path.slice()). slice方法參考
    • 否: 不做處理
  • 到這里,循環遍歷candidates數組
    • 每次將當前的值推入路徑
    • 然后調用dfs函數
    • dfs函數結束之后,要進行回溯操作,即將對path使用pop()方法

var combinationSum = function(candidates, target){let len = candidates.length,path = [],res = []candidates.sort((a,b)=>a-b)function dfs(resides, path, begin){if(resides < 0) returnif(resides == 0) return res.push(path.slice())	// 此處需要返回一個新的數組,不能使用同一個內存中的數組for(let i = begin; i < len ; i++){if(resides - candidates[i] < 0) break;path.push(candidates[i])dfs(resides - candidates[i], path, i)path.pop()}}dfs(target, path, 0)return res       
}

注意: res.push(path)時,由于path是個引用類型.因此實際上push進的是一個十六進制地址.可以看做下面:

res[0] = ‘0xffffffff’

當后面回溯path.pop()時, 內存0xffffffff中的值會改變.

最后一次回溯 內存0xffffffff中的值為 []

因此 res[0] = []

而我們需要得到的是res[0] = [a,b,c] 這樣的結構。 因此我們每次在push時,需要重新生成一個數組傳入,即使用path.slice()

栗子 - 數組總和II

題目描述

算法思路:

以傳入參數combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)為栗子進行說明:先將傳入的數組candidates進行升序排列, 即candidates = [1,1,2,5,6,7,10], 采用樹的深度優先遍歷.

• resides: 離target =8 , 差多少
• candicates: 當前的用于操作的候選數組
• path: 當前的路徑
• res: 最終返回的結構

當resides < 0時, 直接退出當前

當resides ===0 時,代表 path中的數組滿足條件. 將path推入res中 res.push(path.slice())

當resides > 0 時, 遍歷candidates數組:

• 每次判斷 resides - candidates[i] 是否大于0 , 若小于0則進行剪枝(退出當前循環)

• 同時要考慮[1,2, 5] 和 [1,7]的情況.因為原數組中有2個1, 只需第一個1即可. if(candidate[i] !== candidate[i-1])

• 到這里就是正常的遞歸回溯工作了:

  • 每次將 candidates[i]推入path中.
  • 然后調用 dfs()遞歸
  • 出來回溯. path.pop()

var combinationSum2 = function(candidates, target) {candidates.sort((a, b) => a - b)var res = []function dfs(resides, candidates, path) {if (resides < 0) returnif (resides === 0) res.push(path.slice())for (let i = 0, len = candidates.length; i < len; i++) {if (candidates[i] !== candidates[i - 1]) {if (resides - candidates[i] < 0) breakpath.push(candidates[i])dfs(resides - candidates[i], candidates.slice(i + 1), path)path.pop()}}}dfs(target, candidates, [])return res
}

栗子 - 組合總和 III

題目參考

算法思路: 還是使用深度優先.

• candidates：當前用于操作的數組
• path: 當前的路徑
• resides: 當前距離目標的差值

每次進入 dfs:

• 首先檢查條件是否滿足:

  • resides若為負數,退出當前環境
  • path.length 若等于 k 則退出當前環境
  • candidates存在且candidates的長度為0,則退出當前環境

• 然后循環candidates,對于每個candidates[i]

  • 得到當前的path = […path, candidates[i]]
  • 計算當前path長度,若等于k 則判斷 resides - candidates[i] 是否為0, 若為0,則將當前路徑推入res中。并退出
  • 遞歸調用 dfs(resides - candidates[i], candidates.slice(i+1), path)
  • 這里需要回溯 path.pop()

var combinationSum3 = function (k, n) {var res = []function dfs(candidates, resides, path) {if ((candidates && candidates.length == 0) || path.length > k || resides < 0) returnfor (let i = 0, len = candidates.length; i < len; i++) {path = [...path, candidates[i]]if (path.length === k && resides - candidates[i] == 0) return res.push(path.slice())dfs(candidates.slice(i + 1), resides - candidates[i], path)path.pop()}}dfs([1, 2, 3, 4, 5, 6, 7, 8, 9], n, [])return res
}

栗子 - 從根到葉子節點數字之和

題目參考

思路:

• 使用 sum 保存總和, r 保存當前樹結構的根節點, path 保存當前的路徑(數組類型)
• 使用dfs深度優先遍歷樹, 對于每次遍歷 dfs(root, path)
  • 判斷r 是否為空,若空則返回,否則執行下一步
  • 更新當前的path = […path, r.val]
  • 判斷當前是否為葉子節點:
    • 若是則: sum += path.join('') - 0. 其中-0是數字的隱式類型轉換
  • dfs(r.left, path)
  • dfs(r.rigth, path)
  • 回溯 path.pop()

var sumNumbers = function (root) {var sum = 0;function dfs(r, val) {if (!r) returnval = [...val, r.val]if (!r.left && !r.right) {return sum += val.join('') - 0}dfs(r.left, val)dfs(r.right, val)val.pop()}dfs(root, '')return sum
};

栗子 - 路徑總和II

題目參考

算法思路:大體的思路是深度優先遍歷,遍歷順序5 -> 4 -> 11 -> 7 --> 11 -> 2 --> 11 --> 4 -->5

其中,->代表下一個-->代表回退。遞歸循環調用dfs函數.傳入當前的樹結構的根節點r、距離總和差值resides和當前的路徑path

每次dfs循環如下:

• 判斷r是否為null, 若是則返回
• 生成當前的path.
• 判斷 resides - r.val 是否為0
  • 若為0,則判斷當前是否是葉子節點
• dfs 當前節點的左節點和右節點

var pathSum = function(root, sum){var res = []function dfs(resides, r, path){if(!r) returnpath = [...path, r.val]		// 這里使用[]隱式規則,在新的內存空間中生成了一個數組if(resides - r.val === 0 && !r.left && !r.right) return res.push(path)dfs(resides - r.val, r.left, path)dfs(resides - r.val, r.right, path)}dfs(sum, root, [])return res
}