Why doesn't my recursive approach work in Python?

Question

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

So why does it append an empty list? Your code has some clear places where the append is happening: inspect those? What happens on a small-input run? At what point in your code does the deviation from expectation happen? What can you reduce that to? — Mike 'Pomax' Kamermans
– Mike 'Pomax' Kamermans, Commented Oct 26, 2021 at 0:42
Welcome to Stack Overflow! As you learn how to write python programs, I suggest you learn how to debug as well. This is a critical skill to have when code doesn't work the way you expect it to. This article has some great tips on how to get started. — Code-Apprentice
– Code-Apprentice, Commented Oct 26, 2021 at 0:48
@Mike'Pomax'Kamermans I tested the subsets that were deemed valid, hence the commented out print statement. I don't understand how appending a valid non-zero-length subset to res could result in an empty list. — HalfMillennium
– HalfMillennium, Commented Oct 26, 2021 at 0:51

inteoryx · Accepted Answer · 2021-10-26 01:00:50Z

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!

Collectives™ on Stack Overflow

Why doesn't my recursive approach work in Python?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related