CODEWITHSUNDEEP
pythonalgorithmrecursiondepth-first-search
Spencer Davis
Spencer Davis

Reputation: 171

Not understanding this recursive python code

I recently was trying to figure out the answer to a question on code fights. I eventually found a solution that works from this website: https://statyang.wordpresults.com/python-practice-51-combination-sum/

However, no matter how many print statements or debugging I do, I can't seem to figure out how 

target

is changing value somewhere in the 

if target < candidates[i]:
    return

The whole purpose of the program is to have an input of an array, and including duplicates, output the different combinations of sums that add up to the target.

here is the code with all of the debugging print statements

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))

here is the ending output

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

as you can see, each of these pairs add up to 8

so really confused as to how the value for target seems to change somewhere inside of the loop and always to a positive number even though it is always inserting

 target - candidates[i]

inside of the recursive function

Upvotes: 0

Views: 152

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

The recursion starts with this call, self.DFS(candidates,target,0,result,[]), where the parameter, intermedia, is an empty array.

intermedia then accumulates another candidate whenever target is still greater than or equal to candidate[i]. The accumulation happens at the end of this line: self.DFS(candidates,target-candidates[i],i,result,intermedia+[candidates[i]]).

Meanwhile, target is decreased for this particular call to represent that we've used the candidate in trying to reach the target number. So that when target==0, we're ready to result.append(intermedia), which is this particular accumulation of candidates. A full new set of recursive calls with different candidates is generated in each call by the for loop.

Upvotes: 1

sjcrowe
sjcrowe

Reputation: 41

target is only changing via the recursive call on this line:

self.DFS(candidates,target-candidates[i],i,result,intermedia+[candidates[i]])

It's always positive because the program does this check before making the recursive call:

    if target<candidates[i]:
        ...
        return

Upvotes: 0

Related Questions