内容简介:大意:给定一组不含重复数字的数组和一个目标数字,在数组中找出所有数加起来等于给定的目标数字的组合。由于我们需要找到多个组合,简单的使用用回溯算法解决问题的一般步骤:
题目描述
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
循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。
用回溯算法解决问题的一般步骤:
- 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。
- 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
- 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。
根据题目的描述我们知道它满足了我们所说的步骤一,下面我们来确定搜索的思路:point_down:
搜索的思路
回溯一般需要遍历所有的情况来找出问题的解,在写代码之前我们不妨先画出一个递归树,理清我们写代码的思路:point_down:
由于数组中的数字是可以被重复使用的,所以对于同一个数字也要向下递归。但是,对于 [2,2,3]
和 [2,3,2]
这样的结果 其实是重复的,我们需要剔除掉重复的项。
可以这样优化递归树:point_down:
其他问题
如何保存数据
刚刷题目的时候看到这类多种解的问题经常会感到懵逼,其实这里通常的解法是传入一个 临时数组 ,进入递归前 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绝大多数回溯题目
- 常用算法之回溯法
- [经典算法]8皇后问题sql求解(回溯算法)
- LeetCode37 使用回溯算法实现解数独,详解剪枝优化
- LeetCode46 回溯算法求全排列,这次是真全排列
- 数据结构与算法(七):迷宫回溯和八皇后问题
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!