题目描述
Given a set of candidate numbers (
candidates
) (without duplicates) and a target number (target
), find all unique combinations incandidates
where the candidate numbers sums totarget
.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
循环肯定是不行的,这时候我们可以使用回溯算法来解决这个问题。
用回溯算法解决问题的一般步骤:
- 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。
- 确定易于搜索的解空间结构, 使得能用回溯法方便地搜索整个解空间。
- 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。
根据题目的描述我们知道它满足了我们所说的步骤一,下面我们来确定搜索的思路????
搜索的思路
回溯一般需要遍历所有的情况来找出问题的解,在写代码之前我们不妨先画出一个递归树,理清我们写代码的思路????
由于数组中的数字是可以被重复使用的,所以对于同一个数字也要向下递归。但是,对于 [2,2,3]
和 [2,3,2]
这样的结果 其实是重复的,我们需要剔除掉重复的项。
可以这样优化递归树????
其他问题
如何保存数据
刚刷题目的时候看到这类多种解的问题经常会感到懵逼,其实这里通常的解法是传入一个 临时数组 ,进入递归前 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 老师的前端补习班」关注我的微信公众号,那么就可以第一时间收到我的最新文章。