0

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

Improve this question

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Yes I am still confused on what exactly makes target go from 0 to another positive number?
@SpencerDavis each function call gets its own target variable assigned. Once the initial function call passes 8 as the first target to DFS, the for loop generates four unique DFS calls, with targets (8-8), (8-6), (8-4), (8-2), according to the current target and candidate. The one where target equals zero, does not go on to more recursion because of the early return, which ends that branch. Each of the three other calls go on to the loop, following its conditions, each with a different target.
thanks @גלעד ברקן for explaining that. so to continue, I do understand that each function gets its own target and see how 8-8, then 8-6,e tc.. and yes I was confused about the return so I understand more now thanks. However, after it gets to 0 since you said "Each of the three other calls go on to the loop, following its conditions, each with a different target" ... I didn't explicitly increase the target in the code. My only question is exactly what is increasing the target?
@SpencerDavis target could only increase if one of the candidates was negative since the operation is target - candidates[i]. In your example, perhaps you are mistaking the order in which you see target logged to the console with an increase. target starts with 8, then gets redefined recursively to 8-8, 8-6, 8-4, 8-2; then 8-6-2, 8-4-4, 8-4-2 etc. Notice that I didn't include (8-8-something) since negative results are prevented in the for loop by an additional check.
@SpencerDavis where you see a return, that branch is cutoff there and does not continue executing.
|
0

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
Improve this answer

4 Comments

when I was debugging it looked like after it hit the if statement, it didn't hit the recursion line and went right to the loop again. Perhaps every print statement is not displayed because if there were no recursion, the "return" would simply end the loop. Since this is looping again, the only thing that could do that is recursion? Still confused on if target is 0 and I am inputting essentially 0 - 4 inside of DFS, then what part of the "if statement" is making it positive?
one thing I would recommend would be to add another argument to the DFS function, maybe call it indent, in the first call to DFS, pass '' and in the recursive call pass indent+' '. Then put indent+ at the beginning of all your print statements. This (or some variant) is something I often use when printing from a recursively called function, and makes it much more clear what's going on.
that sounds like a great idea. I have to say though that I conceptually have an idea of what you are talking about, but don't exactly know what you mean when you say indent. it sounds like you are saying to add another argument to DFS which is fine, but indent is a keyword isn't it? and don't know what indent+ means. So I would love it if you could either provide a link or perhaps comment an example in code of what you mean. It sounds like a great idea though.
indent isn't a keyword as far as I know, it was just a variable name I chose arbitrarily. Specifically my recommendation would be that in the DFS call in line 8, instead do: self.DFS(candidates,target,0,result,[],'') the line 11 would be: def DFS(self,candidates,target,start,result,intermedia,indent): and line 39 would be: self.DFS(candidates,target-candidates[i],i,result,intermedia+[candidates[i]],indent+' ') and all the "print" lines from line 12 to 38, you would add "indent + " like so: print indent + "===== inside DFS method ============="

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.