美文网首页
39.联合的和

39.联合的和

作者: New_Learner | 来源:发表于2019-05-16 15:13 被阅读0次

    给定一组候选的数和一个目标和,使用候选的数(不限个数,不限次数)相加得到目标和,并返回所有可能的加法。

    /*

    这是一个递归算法,算法的三部分,起始条件,终止条件和递归。

    首先看起始条件:显然就是从i=0开始递归

    终止条件:一旦target<每个元素的时候,不存在更深层的递归了;而当target=0时,说明加法完成了,返回正确的解。

    递归基:实际上是对每个元素都做了一次递归,对target-那个元素对该元素以后的数组再进行计算。

    这个递归比较巧妙的地方在于,对于第i个元素,再进行递归的时候还是从第i个元素开始算起的,这样就可以保证数字是可以重复的,但是又不会重复加法。

    */

    利用 DFS 来计算该题:

    稍微提一句这里为什么要pop,是因为如果没有正确的解的话,根据递归,这里就会return,虽然res还没有被存储,但是path已经被污染了,实际上这是一个试错的过程。每个值输入都要被pop,如果满足条件再进入深层。

    相关文章

      网友评论

          本文标题:39.联合的和

          本文链接:https://www.haomeiwen.com/subject/amguaqtx.html