Why doesn't my recursive approach work in Python?-CodePudding

I've been racking my brain trying to figure out why these two approaches in solving a Leetcode problem (Combination Sum), despite looking virtually the same. The first approach (working) takes in extra parameters that do not appear to be necessary. I have checked my code with print statements, and subsets with the required total are found, but for some reason, the result is not properly appended to res. Instead of appending the valid subset, it appends an empty list. I'm sure the answer is simple, but I cannot seem to find the logical difference. Here's both methods:

def combinationSumWorking(candidates, target):
    result = []
    def combinationUtil(index, numbers, sumSoFar):
        if sumSoFar > target:
            return
        if sumSoFar == target:
            #print("working",numbers)
            result.append(numbers)
            return
        for i in range(len(candidates)):
            combinationUtil(i, numbers [candidates[i]], sumSoFar candidates[i])
    
    combinationUtil(0,[],0)
    return result

def combinationSumMine(candidates, target):
    res = []
    def findCombos(subset):
        if(sum(subset) > target):
            subset = []
            return
        if(sum(subset) == target):
            res.append(subset)
            #print("mine",subset)
            subset = []
            return
        for i in range(len(candidates)):
            subset.append(candidates[i])
            findCombos(subset)
            subset.pop()
    findCombos([])
    return res
    
print(combinationSumMine([2,3,6,7],7))
print(combinationSumWorking([2,3,6,7],7))

The result is:

[[], [], [], []]
[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]

CodePudding user response：

Your problem is doing the append, then the recursive call, and then popping. I'll explain in a second. Here's a version of your code that gets your expected result:

def combinationSumMine(candidates, target):
res = []
def findCombos(subset):
    if(sum(subset) > target):
        return
    if(sum(subset) == target):
        res.append(subset)
        return
    for i in range(len(candidates)):
        findCombos(subset   [candidates[i]] )
        
findCombos([])
return res

print(combinationSumMine([2,3,6,7],7))

What's happening is, you iterate through the list of candidates appending a new value to your subset list and then you make the recursive call. So, when that recursive call executes it's executing with the list you already added one of the candidates to. Likewise, when, or if, you find a result, you append the same "subset" list to your result. When you "pop" a value off, you're popping it off the subset that's in your result. That's why you'll always return an empty answer.

What you want to do instead is create a copy of the subset list. One way to do that, in my example, is, instead of providing the subset list to the findCombos function I supply the result of concatenating the subset list to a list containing the new element we want to consider. That's an entirely new list!