python - 不理解这个递归的python代码

Question

我最近试图找出有关代码冲突问题的答案。我最终找到了一个适用于该网站的解决方案: https://statyang.wordpresults.com/python-practice-51-combination-sum/

然而，无论我做了多少打印语句或调试，我似乎都想不通

target

正在改变某处的值

if target < candidates[i]:
    return

该程序的全部目的是输入一个数组，包括重复项，输出加起来等于目标的总和的不同组合。

这是包含所有调试打印语句的代码

class Solution2:
# @param candidates, a list of integers
# @param target, integer
# @return a list of lists of integers
def combinationSum(self, candidates, target):
    candidates.sort()
    result=[]
    self.DFS(candidates,target,0,result,[])
    return result

def DFS(self,candidates,target,start,result,intermedia):
    print "===== inside DFS method ============="
    print "candidates {0}".format(candidates)
    print "target: {0}".format(target)
    print "start {0}".format(start)
    print "result {0}".format(result)
    print "intermedia {0}".format(intermedia)
    if target==0:
        print ">>> inside if target==0"
        print "target==0 appending {0}".format(intermedia)
        result.append(intermedia)
        return
    for i in range(start,len(candidates)):
        print "=====inside for loop ========: i= {0}".format(i)
        print "target={0}, cadidates[i]={1}".format(target, candidates[i])
        if target<candidates[i]:
            print ">>> target < candidates[i] {0} < {1}".format(target, candidates[i])
            print "i before return {0}".format(i)
            return
        print "i after return {0}".format(i)
        print "======== preparing for recursion ========:"
        print "candidates {0}".format(candidates)
        print "new target: target - candidates[i]: {0} - {1} = {2}".format(target, candidates[i], target-candidates[i])
        print "new start: {0}".format(i)
        print "result {0}".format(result)
        print "new intermedia: intermedia + candidates[i]: {0} + {1} = {2}".format(intermedia, [candidates[i]], intermedia + [candidates[i]])
        print "i= {0} start= {1}".format(i, start)
        print "about to call recursion again!"
        self.DFS(candidates,target-candidates[i],i,result,intermedia+[candidates[i]])

test2=Solution2()
print(test2.combinationSum([2, 4, 6, 8], 8))

这是结束输出

[[2, 2, 2, 2], [2, 2, 4], [2, 6], [4, 4], [8]]

如你所见，每一对加起来都是 8

对于 target 的值似乎如何在循环内部的某处发生变化并且始终为正数，即使它总是插入，真的很困惑

 target - candidates[i]

递归函数内部

Answer 1

递归从这个调用开始，self.DFS(candidates,target,0,result,[])，其中参数intermedia是一个空数组.

intermedia 然后在 target 仍然大于或等于 candidate[i] 时累积另一个 candidate。累积发生在这一行的末尾:self.DFS(candidates,target-candidates[i],i,result,intermedia+[candidates[i]])。

同时，对于此特定调用，target 会减少，以表示我们已使用候选人来尝试达到目标号码。这样当 target==0 时，我们就准备好 result.append(intermedia) 了，也就是这个特定的候选积累。 for 循环在每次调用中生成一组全新的具有不同候选者的递归调用。