Subset problem in python - fix the number of addends that sum to the target

Question

I'm trying to implement a simple program that aims to solve the subset problem in python. I've found the following code that involves dynamically programming:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print("sum(%s)=%s" % (partial, target))
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 

The code works but it finds all the possible combinations, while I'm only interested on subsets with a maximum number of addends that I want to specify time to time.

In other words I'd like to set a maximum number of the internal loops. To do that I've written the following code that considers all the possible combinations of at most 4 numbers that sum to the target (i.e. 3 internal loops)

def subset_sum(n_list, tot):

    cnd = n_list[n_list < tot]
    s = np.sort(cnd)
    n_max = len(cnd)

    possibilities = []

    for i1 in range(n_max):
        i2 = i1+1

        while (i2<n_max)and(s[i1]+s[i2]<=tot):
            if (s[i1]+s[i2]==tot):
                possibilities.append([s[i1],s[i2]])
            i3 = i2+1

            while (i3<n_max)and(s[i1]+s[i2]+s[i3]<=tot):
                if (s[i1]+s[i2]+s[i3]==tot):
                    possibilities.append([s[i1],s[i2],s[i3]])
                i4 = i3+1

                while (i4<n_max)and(s[i1]+s[i2]+s[i3]+s[i4]<=tot):
                    if (s[i1]+s[i2]+s[i3]+s[i4]==tot):
                        possibilities.append([s[i1],s[i2],s[i3],s[i4]])

                    i4+=1
                i3+=1
            i2+=1 
    return possibilities

This code works pretty well, can also be speed up with numba (while the first code no) but I cannot fix the maximum number of addends. Is there a way to implement the function subset_sum with an extra argument that fix the maximum number of addends that sum to the target?

Answer 1

Since you are adding a number in each recursion you can just limit the recursion depth. To do so, you need to add a new parameter to control the maximum depth (a.k.a. the maximum number of addends).

Here is the code:

def subset_sum(numbers, target, num_elems, partial=[]):
    # Check if the partial sum is equals to target                                                                                                                                                                                          
    s = sum(partial)
    if s == target:
        print("sum(%s)=%s" % (partial, target))

    # If we have surpassed the number there is no point to continue
    if s >= target:
        return
    # If we have surpassed the number of elements there is no point to continue
    if len(partial) >= num_elems:
        return

    # Otherwise go through the remaining numbers
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, num_elems, partial + [n]) 

You can run it with:

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    num_elems = 3
    target = 10
    p = []
    subset_sum(nums, target, num_elems, p)

And the output will be:

sum([1, 4, 5])=10
sum([2, 3, 5])=10

Notice that the combination of 4 elements ([1, 2, 3, 4]) is not shown.

---

EDIT:

To speed-up the above code with Numba you need to build an iterative version of it. Since you are basically computing the combinations of numbers in sets of num_elements size, you can check the iterative implementation of the itertools.combination (more details here). Based on that implementation you can obtain the following code:

def subset_sum_iter(numbers, target, num_elements):
    # General: we iterate among the indexes and build each solution by taking the values in those indexes

    # Initialize solutions list
    solutions = []

    # Build first index by taking the first num_elements from the numbers
    indices = list(range(num_elements))
    solution = [numbers[i] for i in indices]
    if sum(solution) == target:
        solutions.append(solution)

    # We iterate over the rest of the indices until we have tried all combinations
    while True:
        for i in reversed(range(num_elements)):
            if indices[i] != i + len(numbers) - num_elements:
                break
        else:
            # No combinations left
            break

        # Increase current index and all its following ones
        indices[i] += 1
        for j in range(i + 1, num_elements):
            indices[j] = indices[j - 1] + 1

        # Check current solution
        solution = [numbers[i] for i in indices]
        if sum(solution) == target:
            solutions.append(solution)

    # Print all valid solutions
    for sol in solutions:
        print ("sum(" + str(sol) + ")=" + str(target))

Which can be run with:

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]
    num_elems = 3
    target = 10

    # Calling iterative subset
    subset_sum_iter(nums, target, num_elems)

And outputs:

sum([1, 4, 5])=10
sum([2, 3, 5])=10

As in the previous case, notice that only the combinations with 3 elements are shown.

Answer 2

I am not sure whether you prefer combinations or permuations here, but you could try this?

import itertools
limit = 1 #number of addends
possibilities = 0
combinations = []
not_possibilties = 0
number_addends = 4
while(limit <= number_addends):
    for comb in itertools.combinations([number_list], limit):
        if sum(comb) == target:
            possibilities +=1
            combinations.append(comb)
        else:
            not_possiblitities +=1
    limit +=1
total_combi = possibilities + not_possibilties #check if actually all possibilities were done

If you need permutations just change itertools.combinations to itertools.permutationss