LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

栏目: 编程工具 · 发布时间: 5年前

内容简介:大意:给定一组不含重复数字的数组和一个目标数字,在数组中找出所有数加起来等于给定的目标数字的组合。由于我们需要找到多个组合,简单的使用用回溯算法解决问题的一般步骤:

题目描述

Given a set of candidate numbers ( candidates ) ( without duplicates ) and a target number ( target ), find all unique combinations in candidates where the candidate numbers sums to target .

The same repeated number may be chosen from candidates unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

大意:给定一组不含重复数字的数组和一个目标数字,在数组中找出所有数加起来等于给定的目标数字的组合。

输入

candidates = [2,3,6,7], target = 7

输出

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

分析题目

由于我们需要找到多个组合,简单的使用 for 循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。

用回溯算法解决问题的一般步骤:

  1. 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。
  2. 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
  3. 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

根据题目的描述我们知道它满足了我们所说的步骤一,下面我们来确定搜索的思路:point_down:

搜索的思路

回溯一般需要遍历所有的情况来找出问题的解,在写代码之前我们不妨先画出一个递归树,理清我们写代码的思路:point_down:

LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

由于数组中的数字是可以被重复使用的,所以对于同一个数字也要向下递归。但是,对于 [2,2,3][2,3,2] 这样的结果 其实是重复的,我们需要剔除掉重复的项。

可以这样优化递归树:point_down:

LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)

其他问题

如何保存数据

刚刷题目的时候看到这类多种解的问题经常会感到懵逼,其实这里通常的解法是传入一个 临时数组 ,进入递归前 push 一个结果,结束之前可以用一个 全局数组 保存下来,结束之后在 临时数组pop 掉它。

如何确定结束条件

结束条件通常题目中就会给出,一般来说找到给出的解或者递归层数达到上限就可以结束递归

示例代码

function foo (nums, target) {
    let result = []
    
    dfs(0, 0, [])
    return result
    
    function dfs (index, sum, tmp) {
        if (sum === target) {
            result.push(tmp.slice())
        }
        if (sum > target) {
            return
        }
        for (let i = index; i < nums.length; i++) {
            tmp.push(nums[i])
            dfs(i, sum + nums[i], tmp)
            tmp.pop()
        }
    }
}

总结

对于这类题目,使用回溯算法显然很方便。当然,除了递归之外也能用 或者 队列 来解决。另外,对于前端同学,遇到需要开辟 临时数组 的题目时,如果存在赋值操作,记得返回它的浅复制,如 result.push(tmp.slice()) ,否则会对结果产生影响。

原题地址: Combination Sum

代码不定时更新,欢迎 star 我的 repo

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号,那么就可以第一时间收到我的最新文章。

LeetCode偶尔一题 —— 39. Combination Sum(回溯算法系列)


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Mobilizing Web Sites

Mobilizing Web Sites

Layon, Kristofer / 2011-12 / 266.00元

Everyone has been talking about the mobile web in recent years, and more of us are browsing the web on smartphones and similar devices than ever before. But most of what we are viewing has not yet bee......一起来看看 《Mobilizing Web Sites》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具