Combination Sum和深度優先搜索Depth-First-Search

afishhhhh 發布于2019-08-21 18:20 / 2762人閱讀

摘要：后面又想到了一種方式，一直累減標準答案深度優先搜索算法英語，簡稱是一種用于遍歷或搜索樹或圖的算法。因發明深度優先搜索算法，約翰霍普克洛夫特與羅伯特塔揚共同獲得計算機領域的最高獎圖靈獎。

題目

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

給定一個由正整數組成的數組C和一個目標數字T，查找C中所有的唯一組合，其中候選數字總和為T。

從C中抽出的數字可以無限重復。

來個例子：數組[2, 3, 6, 7] 和目標 7 [2,4,5,8]

需要返回

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

解答

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

標準答案

深度優先搜索算法（英語：Depth-First-Search，簡稱DFS）是一種用于遍歷或搜索樹或圖的算法。沿著一個方向如果有未搜索的節點就一直搜索下去。

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

就像下圖，按照優先級為右下左上順時針的方式嘗試移動，先往右走，但是有堵墻走不了，所以嘗試往下走，如果發現右下左上全都走不了了，就返回到上一個節點進行移動如3 -> 4, 25 -> 26 就是返回到上一個節點。所以遞歸沒得跑了。

在代碼實現上也有標準的模板：

void dfs()  
{  
     // 判斷是否到達終點
     if() {
         return;
     }
 
     // 嘗試每一個可走方向（右下左上） 
     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就把當前的數組記錄下來保存
      result.push(temp.concat())
      return
    } else if (value > target) {
      return
    } else {
      for (let i = index, len = arr.length; i < len; i++) {
        // 記錄下之前累加的數字
        let newtemp = temp.concat(arr[i])
        // 繼續下一步  
        dfs(value + arr[i], i, newtemp)
      }
    }
  }
}
LeetCode上還有性能更加好的解法，大家可以自己去觀摩一番，提高一下姿勢水平。
因發明“深度優先搜索算法”，約翰·霍普克洛夫特與羅伯特·塔揚共同獲得計算機領域的最高獎：圖靈獎。
做完這題最大的感受就是，智商不夠，套路來湊，得把基礎的數據結構和算法知識看熟啰。
ass♂we♂can

云服務器 GPU云服務器深度優先搜索廣度優先搜索最佳優先搜索算法廣度優先搜索算法代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/90368.html

[Leetcode] Combination Sum 組合數之和

摘要：深度優先搜索復雜度時間空間遞歸棧空間思路因為我們可以任意組合任意多個數，看其和是否是目標數，而且還要返回所有可能的組合，所以我們必須遍歷所有可能性才能求解。這題是非常基本且典型的深度優先搜索并返回路徑的題。本質上是有限深度優先搜索。 Combination Sum I Given a set of candidate numbers (C) and a target number (...

GitCafe 2019-08-14 12:31 評論0 收藏0
LeetCode偶爾一題 —— 39. Combination Sum（回溯算法系列）

摘要：輸入輸出分析題目由于我們需要找到多個組合，簡單的使用循環肯定是不行的，這時候我們可以使用回溯算法來解決這個問題。用回溯算法解決問題的一般步驟針對所給問題，定義問題的解空間，它至少包含問題的一個最優解。題目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...

linkin 2019-08-23 18:29 評論0 收藏0
LeetCode 關于回溯問題的看法

摘要：回溯算法在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。回溯算法( BackTrack )在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。使用回溯算法解題的一般步驟使用回溯算法解題的一般步驟：針對所給問題得出一般的解空間用回溯搜索方法搜索解空間使用深度優先去搜索所有解并包含適當的剪枝操作 LeetCode 使用回溯算法的題目主要有 36 題，...

ASCH 2019-08-15 13:43 評論0 收藏0
采用矩陣+深度優先算法解決迷宮問題

摘要：所謂深度優先算法，百科的解答是這樣的深度優先搜索算法，簡稱是搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。這一過程一直進行到已發現從源節點可達的所有節點為止。所謂深度優先算法，百科的解答是這樣的深度優先搜索算法（Depth-First-Search），簡稱DFS,是搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過...

yankeys 2019-08-20 13:54 評論0 收藏0
采用矩陣+深度優先算法解決迷宮問題

摘要：所謂深度優先算法，百科的解答是這樣的深度優先搜索算法，簡稱是搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。這一過程一直進行到已發現從源節點可達的所有節點為止。所謂深度優先算法，百科的解答是這樣的深度優先搜索算法（Depth-First-Search），簡稱DFS,是搜索算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過...

bang590 2019-08-14 17:15 評論0 收藏0