Cannot understand recursive function Python

Question

I have been looking at the solution for this problem (below) for hours and cannot figure out how the recursion works. Can someone please explain in basic terms how it works.

Since group is appended and then popped, isn't the popped list going to just always be equal to nothing []?

# Given a  list of ints, is it possible to choose a group of some of the   
# ints, such that the group sums to the given target?
#   0, 2, 4, 8, 10 -> True                                                  
#   0, 2, 4, 8, 14 -> True                                                  
#   0, 2, 4, 8, 9 -> False   

def sum_checker(ints, total, group, index):
    if sum(group) > total:            # backtracking
        return False
    if index == len(ints):            # BASE CASE
        return sum(group) == total

    group.append(ints[index])
    if sum_checker(ints, total, group, index + 1):
        return True
    group.pop()
    return sum_checker(ints, total, group, index + 1)


ints = [int(input()) for i in range(int(input()))]
total = int(input())
group = []
print(sum_checker(ints, total, group, 0))

Answer 1

isn't the popped list going to just always be equal to nothing []?

Not always. At the third if statement, it recursively adds to the group list, and only when that call stack returns (when the sum of the group exceeds the total, or the index is outside the input range), does the most recent pushed value get popped.

In execution order of the first input , here's the group values

0   
0, 2   
0, 2, 4  
0, 2, 4, 8... Sum is greater than 10, return False   
8 is popped, and the previous index increases      
0, 2, 4.... The index is out of range, and the group sum is not the total
4 is popped and the previous index increases   
0, 2, 8... This is equal to 10, so we return True back up the call stack 

At the end of unwinding the recursion, yes the group list will be empty, but the output only requires a boolean, not tracking the group that matches the criteria

Answer 2

Ok. So let's think this question without real code at first. Just think this strategy:

1. We test each element of ints one by one, checking by picking current value plus previous selection can we get the target sum.
2. For example, ints= [1, 2, 4, 8], target = 11.
3. We try to select 1, we don't know if we can get the target before examine other elements, so we continue to check, holding that 1 in your hands.
4. Now we meet 2, still no idea, just pick and continue.
5. Same for 4.
6. Oops, we have sum=1+2+4+8 = 13 > 11. [1,2,4,8] is a bad selection plan. Let's drop from the end and chek if we have other choices. Drop 8.
7. Now we have sum=1+2+4=7, but we cannot add more elements since we reach the end of ints. Drop 4 to see if more choices are possible.
8. We now hold 1+2 and should check from 8, That's 11! We made it!

So try this process yourself using pencil and paper. The core idea here is to maintain a what-we-have-selected array, which is group in your code, and then to check if we can reach target based on this selection + new elements. If not, modify the what-we-have-selected array and continue.

Answer 3

Regarding your concern about group being appended and popped. Remember that the statement

if sum_checker(ints, total, group, index + 1):

Starts the search again (just this time with the next index). Say with your example.

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[],
    index=0
)

The first time we hit group, we append 0 to group, so we're then calling sum_checker with the arguments.

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[0],
    index=1
)

Then, since group already has one element, we append 2 to group. So we then have:

sum_checker(
    ints=[0, 2, 4, 8],
    total=10,
    group=[0, 2],
    index=2
)

Which means, we start filling up group before we get to .pop(). If the sum() of group becomes too big, THEN we do the first .pop(), and start checking again without the last element that was added.