Function That Find Combination Of Values That Sums To A Given Number

This post Finding Combinations to the provided Sum value presents the function subsets_with_sum(). It finds a combination of values in an array which the sum is equal to a given va

Solution 1:

To start, I'll just add some line breaks to make it a bit easier to read:

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): 
            r.append(l)
        elif t < sum(l): 
            return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

First thing you'll notice is that the subsets_with_sum defines a function and calls it once in the last return statement. The first element is your list from which you sample values, the second is the target sum, and third is an parameter that tells the function whether a single element from lst can be used multiple times.

Because the _a is defined within the subsets_with_sum it is enclosed with the values passed to subsets_with_sum - this is important, lst is the same for every recursive call of _a. The second thing to notice is that l is a list of values, whereas r is a list of lists. Importantly, l is a different object for each _a call (that's due to l + [lst[u]] resulting in a copy of l concatenated with [lst[u]]). However, r denotes the same object for each _a call - r.append(l) modifies it in place.

I'll start with with_replacement == True because I find it simpler. With the first call _a is passed 0, [], [], target. It then checks if t == sum(l) and appends it to r, hence the only elements of r will be lists that sum to t (or target). If sum(l) that recursive branch is discarded by returning None. If the elements of l sum to a value lesser then target then for each element from the lst the element is appended to a copy of l and _a is called with that list. Here's an amended version of the function that prints out the steps, so we can inspect what happens:

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t, c):
        if t == sum(l): 
            r.append(l)
        elif t < sum(l): 
            return
        for u in range(idx, len(lst)):
            print("{}. l = {} and l + [lst[u]] = {}".format(c, l, l + [lst[u]]))
            _a(u + x, l + [lst[u]], r, t, c+1)
        return r
    return _a(0, [], [], target, 0)

Calling subsets_with_sum([1,2,3], 2, True) the following gets printed (I re-ordered and separated the printed lines a bit so they're easier to read):

0. l = [] and l + [lst[u]] = [1]
0. l = [] and l + [lst[u]] = [2]
0. l = [] and l + [lst[u]] = [3]

1. l = [1] and l + [lst[u]] = [1, 1]
1. l = [2] and l + [lst[u]] = [2, 2]
1. l = [2] and l + [lst[u]] = [2, 3]
1. l = [1] and l + [lst[u]] = [1, 2]
1. l = [1] and l + [lst[u]] = [1, 3]

2. l = [1, 1] and l + [lst[u]] = [1, 1, 1]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 2]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 3]

You can see that the right column (l + [lst[u]]) at a level c is equal to the left column (l) at a level c + 1. Furthermore, observe that [3] - the last line where c == 0 doesn't make it past the elif t < sum(l), hence it doesn't get printed. Similarly, [2] at c == 1 gets appended to r, but nonetheless the branch continues to the next level, since one or more elements of the lst might be equal to 0, hence appending them to [2] might result in another list that sums to the target.

Also, observe that for each list at certain level c, whose last element is lst[u] will appear len(lst) - u-times at the next level, c + 1, because that's the number of combinations of the list for each lst[z], where z >= u.

So what happens with with_replacement == False (the default case)? Well, in that case each time lst[u] is added to l and sum(l) < t, so that that specific instance of l continues to the next recursion level only lst[z] can be added to the list, where z > u, since u + 1 is passed to the respective _a call. Let's look what happens when we call subsets_with_sum([1,2,3], 2, False):

0. l = [] and l + [lst[u]] = [1]
0. l = [] and l + [lst[u]] = [3]
0. l = [] and l + [lst[u]] = [2]

1. l = [1] and l + [lst[u]] = [1, 1]
1. l = [1] and l + [lst[u]] = [1, 2]
1. l = [1] and l + [lst[u]] = [1, 3]
1. l = [2] and l + [lst[u]] = [2, 2]
1. l = [2] and l + [lst[u]] = [2, 3]

2. l = [1, 1] and l + [lst[u]] = [1, 1, 1]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 2]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 3]

Now observe that for each list at certain level c, whose last element is lst[u] will appear len(lst) - u - 1-times at the next level, c + 1, because that's the number of combinations of the list for each lst[z], where z > u. Compare this with the with_replacement=True analyzed above.

I suggest you play around with it somewhat more until you understand it better. Regardless of substitution, what is important to realize is that the return statements always return to the caller. The first call of the _a returns to the subsets_with_sum which then returns to the caller (presumably you or some other function). All other (recursive) calls to _a return to the previous instances of _a calls which just discard the returned value (or more precisely, don't bother to do anything with it). The reason you get back the right r is because it behaves somewhat like a global value - each _a call that finds a solution, adds it to the same r.

Finally, the subsets_with_sum doesn't work exactly like I'd expect it to based on its desired functionality. Try the following two calls: subsets_with_sum([2,2,1], 5, True) and subsets_with_sum([2,2,1,1,1], 5, False).