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(回溯算法系列)


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

查看所有标签

猜你喜欢:

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

计算机系统基础

计算机系统基础

袁春风 / 机械工业出版社 / 2014-7-1 / CNY 49.00

《计算机类专业系统能力培养系列教材:计算机系统基础》主要介绍与计算机系统相关的核心概念,解释这些概念如何相互关联并最终影响程序执行的结果和性能。共分8章,主要内容包括数据的表示和运算、程序的转换及机器级表示、程序的链接、程序的执行、存储器层次结构、虚拟存储器、异常控制流和I/O操作的实现等。内容详尽,反映现实,概念清楚,通俗易懂,实例丰富,并提供大量典型习题供读者练习。本书可以作为计算机专业本科或......一起来看看 《计算机系统基础》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具