给定一组候选的数和一个目标和,使用候选的数(不限个数,不限次数)相加得到目标和,并返回所有可能的加法。
/*
这是一个递归算法,算法的三部分,起始条件,终止条件和递归。
首先看起始条件:显然就是从i=0开始递归
终止条件:一旦target<每个元素的时候,不存在更深层的递归了;而当target=0时,说明加法完成了,返回正确的解。
递归基:实际上是对每个元素都做了一次递归,对target-那个元素对该元素以后的数组再进行计算。
这个递归比较巧妙的地方在于,对于第i个元素,再进行递归的时候还是从第i个元素开始算起的,这样就可以保证数字是可以重复的,但是又不会重复加法。
*/
利用 DFS 来计算该题:
稍微提一句这里为什么要pop,是因为如果没有正确的解的话,根据递归,这里就会return,虽然res还没有被存储,但是path已经被污染了,实际上这是一个试错的过程。每个值输入都要被pop,如果满足条件再进入深层。
网友评论