一起lintcode! --------- Combination Sum, Combination Sum II (浅谈递归,以及python中的一个深坑)


  • 太阁x英雄榜

    Combination Sum, Combination Sum II这两个问题是典型的排列组合问题。说到排列组合问题说白了都是套路,也有现成的模板可以用。虽然说不鼓励背题,但是同一类题型总结些经典的套路,深入分析后举一反三还是十分有必要的。说到求解排列组合问题的方法,其实用的最多的是DFS(深度优先搜索),而DFS本身就是通过递归来实现了。 刚开始写码的同学,肯定对递归十分头痛,我也经历过这个时期。(现在很多时候,代码也经常出bug)。但很多代码通过递归实现还是十分便捷。

    我觉得编写一个递归程序最重要的有三方面。首先明确递归函数的功能,即这个递归函数做了什么,返回值是什么?其次,递归出口是什么,我们以什么条件来结束这个递归。最后,分支剪枝,我们怎么去除一些完全不用考虑的情况。

    下面以Combination Sum 为例,讲述下一个典型的排列组合模板:

    def combinationSum(self, candidates, target):
        # 记住首先先要排序,这样可以把相同的元素排在一起,方便去重的检验
        candidates.sort()
        #这里Solution.ret 相当定义了一个全局变量,用来存储最终的结果当然也可以直接将result作为参数传进去
        Solution.ret = []
       #用来记录求和过程
        sum = 0
        self.DFS(sum, candidates, target, 0, [])
        return Solution.ret
    
    def DFS(self,sum, candidates, target, start, valuelist):
        length = len(candidates)
       #当累加和达到目标值后,将中间结果记录下来
        if target == sum:
            return Solution.ret.append(valuelist[:])
        #如果累加和超过目标值则终止本轮计算
        if target < sum:
            return
        #值得注意的是,这里必须将循环的起始点设置为一个参数,这样才能实现多层循环的嵌套遍历
        for i in range(start, length):
            # 剪枝,如果目标值比当前值还小,则退出循环。这里因为元素都为正也算是有贪心的思想在里边。
            if target < candidates[i]:
                return
            #求和
            sum += candidates[i] 
            #加入当前元素
            valuelist.append(candidates[i])
            self.DFS(sum, candidates, target, i, valuelist)
            #移除末尾的元素
            tmp = valuelist.pop()
            sum -= tmp
    

    这里面都是套路,特别是对于排列组合问题问题来说,下面的代码是解决问题的核心,pop操作表示在递归到最深一层后,把路径的最后一个元素移除,然后重新尝试其他可能路径。

            #加入当前元素
            valuelist.append(candidates[i])
            self.DFS(sum, candidates, target, i, valuelist)
            #移除末尾的元素
            tmp = valuelist.pop()
    

    对于 Combination Sum II 来说,由于candidates中的元素只能使用一次,因此我们只需要更新dfs中的代码,做两部分的修改,一个是对start值在下个循环中增加+1,即跳跃到下个元素。而是增加一个去重的剪枝判断(因为candidate中有重复的代码,因此在如果出现相邻两个元素相同的情况,我们应该直接跳过)。

    def dfs(self, candidates, target, start, result, path):
        if (target == 0):
            result.append(path[:])
            return 
        prev = - 1
        for i in range(start, len(candidates)):
            if (candidates[i] > target):
                return
            if (prev != -1 and prev == candidates[i]):
                continue
            path.append(candidates[i])
            self.dfs(candidates, target - candidates[i], i + 1, result, path)
            path.pop()
            prev = candidates[i]
    

    注意:

            if (prev != -1 and prev == candidates[i]):
                continue
    

    上述代码的作用就是检测相邻元素是否相同,如果相同则跳过去

    最后说说python中关于list传递的问题。我在最开始编写代码的时候遇到了一个调试很久的bug。就是传递到result中的元素最后都消失了,这让我头痛了好久。最开始我向result增加元素的方式是通过如下的方式:

          result.append(path)
    

    但实际上这种方式是错误的,我只是相当于把path的引用给了result。由于在接下来,我做了path做了pop操作,result中的结果也发生了改变,为了方便理解,大家可以参考下面的简单代码:

    程序1:

    x = []
    y = ['a','b']
    x.append(y)
    print(x)
    y.pop()
    print(x)
    

    输出结果:

    [['a', 'b']]
    [['a']]
    

    程序2:

    x = []
    y = ['a','b']
    x.append(y[:])
    print(x)
    y.pop()
    print(x)
    

    输出结果:

    [['a', 'b']]
    [['a', 'b']]
    

    这里还有另外一个疑问,是否我一旦对b进行修改就会造成这样的问题呢?

    程序3:

    x = []
    y = ['a','b']
    x.append(y[:])
    print(x)
    print (id(y))
    y = ['c']
    print (id(y))
    y.pop()
    print (id(y))
    print(x)
    

    输出结果:

    [['a', 'b']]
    60624584
    57365448
    57365448
    [['a', 'b']]
    

    从输出结果上来看,对y的赋值操作并没有对x的结果产生影响,同时从变量在内存中的地址可以看出,该赋值操作创建了一个变量y,和之前的y不一样。而pop操作则不产生新的对象。这就是最大的区别。


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待