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

afishhhhh 发布于2019-08-21 18:20 / 2753人阅读

摘要：后面又想到了一种方式，一直累减标准答案深度优先搜索算法英语，简称是一种用于遍历或搜索树或图的算法。因发明深度优先搜索算法，约翰霍普克洛夫特与罗伯特塔扬共同获得计算机领域的最高奖图灵奖。

题目

最近在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云服务器深度优先搜索广度优先搜索最佳优先搜索算法广度优先搜索算法代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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