Combination Sum和深度優(yōu)先搜索Depth-First-Search

afishhhhh 發(fā)布于2019-08-21 18:20 / 2757人閱讀

摘要：后面又想到了一種方式，一直累減標(biāo)準(zhǔn)答案深度優(yōu)先搜索算法英語(yǔ)，簡(jiǎn)稱是一種用于遍歷或搜索樹(shù)或圖的算法。因發(fā)明深度優(yōu)先搜索算法，約翰霍普克洛夫特與羅伯特塔揚(yáng)共同獲得計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)圖靈獎(jiǎng)。

題目

最近在LeetCode上看到這么一道鏈接題目

給定一個(gè)由正整數(shù)組成的數(shù)組C和一個(gè)目標(biāo)數(shù)字T，查找C中所有的唯一組合，其中候選數(shù)字總和為T。

從C中抽出的數(shù)字可以無(wú)限重復(fù)。

來(lái)個(gè)例子：數(shù)組[2, 3, 6, 7] 和目標(biāo) 7 [2,4,5,8]

需要返回

[
  [7],
  [2, 2, 3]
]

解答

看完題目一開(kāi)始想的是把7%2，如果余0或者有與余數(shù)相等的值做為一個(gè)解。如 7%2=1, 2 + 1 = 3 --> [2, 2, 3], 但是一碰到數(shù)組[2, 4, 5] 和目標(biāo) 8的情況解歇菜了。
后面又想到了一種方式，一直累減：x_x

標(biāo)準(zhǔn)答案

深度優(yōu)先搜索算法（英語(yǔ)：Depth-First-Search，簡(jiǎn)稱DFS）是一種用于遍歷或搜索樹(shù)或圖的算法。沿著一個(gè)方向如果有未搜索的節(jié)點(diǎn)就一直搜索下去。

深度優(yōu)先的主要思想就是“不撞南墻不回頭”，“一條路走到黑”，如果遇到“墻”或者“無(wú)路可走”時(shí)再去走下一條路。

就像下圖，按照優(yōu)先級(jí)為右下左上順時(shí)針的方式嘗試移動(dòng)，先往右走，但是有堵墻走不了，所以嘗試往下走，如果發(fā)現(xiàn)右下左上全都走不了了，就返回到上一個(gè)節(jié)點(diǎn)進(jìn)行移動(dòng)如3 -> 4, 25 -> 26 就是返回到上一個(gè)節(jié)點(diǎn)。所以遞歸沒(méi)得跑了。

在代碼實(shí)現(xiàn)上也有標(biāo)準(zhǔn)的模板：

void dfs()  
{  
     // 判斷是否到達(dá)終點(diǎn)
     if() {
         return;
     }
 
     // 嘗試每一個(gè)可走方向（右下左上） 
     for(i=0; i
然后再把我們題目往模板里面一套
var combinationSum = function(candidates, target) {
  let result = []
  let temp = []
  dfs(0, 0, temp)
  return result

  function dfs(value, index, temp) {
    // 判斷累加和是否為target 或者 超出了 target
    if (value === target) {
      // 如果和為target就把當(dāng)前的數(shù)組記錄下來(lái)保存
      result.push(temp.concat())
      return
    } else if (value > target) {
      return
    } else {
      for (let i = index, len = arr.length; i < len; i++) {
        // 記錄下之前累加的數(shù)字
        let newtemp = temp.concat(arr[i])
        // 繼續(xù)下一步  
        dfs(value + arr[i], i, newtemp)
      }
    }
  }
}
LeetCode上還有性能更加好的解法，大家可以自己去觀摩一番，提高一下姿勢(shì)水平。
因發(fā)明“深度優(yōu)先搜索算法”，約翰·霍普克洛夫特與羅伯特·塔揚(yáng)共同獲得計(jì)算機(jī)領(lǐng)域的最高獎(jiǎng)：圖靈獎(jiǎng)。
做完這題最大的感受就是，智商不夠，套路來(lái)湊，得把基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)看熟啰。
ass♂we♂can