Find All Combinations of Numbers That Uniquely Sum to a Set of Numbers

Question

I have a list of numbers (source set), and someone took some or all of those numbers and summed them randomly to make a smaller set of numbers (target set). I have the source set and the target set, but I need to figure out what combination was used. Difficulty: I can't guarantee that all numbers in the source set were used to make the target set, and I can't guarantee that all numbers in the target set came from the source set. Here's a simple example:

• Source Set = 1,2,3,4,5
• Target Set = 3,8
• Result:
  • ResultSet1: Sum([1,2])=3 Sum([3,5])=8 NotFound([]) NotUsed([4])
  • ResultSet2: Sum([3])=3 Sum([1,2,5])=8 NotFound([]) NotUsed([4])
  • ResultSet3: Sum([1,3,4])=8 NotFound([3]) NotUsed([2,5])
• Invalid answers:
  • InvalidSet1: Sum([1,2])=3 Sum([3])=3 Sum([3,5])=8 NotFound([]) NotUsed:[4]
    • Reason: each number from the source set may only be used once to create any target in a given result set

I have found some great examples for deriving the above given a single target value, but I can't find a way to do it with an array of target values rather than a single value (and my coding skills are unfortunately not up to the task). The best start I have is this question, with the code below (note that I removed the s >= target check to accommodate my data):

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

if __name__ == "__main__":
    subset_sum([1,2,3,4,5],4)

This will output:

sum([1, 3])=4
sum([4])=4

I've made some valiant attempts at adding a second layer of recursion to support an array for the target, but I won't embarrass myself by putting the failures here.

I understand that the above code has limitations, and I'm open to solutions based on this code, or completely new code, and output in just about any logical format. Python is strongly preferred, but I would entertain just about anything (note: java gives me hives).

Answer 1

You mean something like:

In []:
import itertools as it

source = [1, 2, 3, 4, 5]
targets = [3, 8]

p = [[a for n in range(1, len(source)) for a in it.combinations(source, n) if sum(a) == t] for t in targets]
[dict(zip(targets, a)) for a in it.product(*p) if len(sum(a, tuple())) == len(set(sum(a, tuple())))]

Out[]:
[{3: (3,), 8: (1, 2, 5)}, {3: (1, 2), 8: (3, 5)}]

Answer 2

The only way I found is quite inefficient, and I'm pretty sure there has to be a smarter way, but it works.

The idea is to get all combinations, get the ones for the first number, go through all of them, remove the used numbers from the list, generate all combinations, get those that match the second number and iterate.

Here's the code. Again, quite ugly but it does the job:

from collections import defaultdict
import itertools as it

def get_all_combinations(l):
    return [a for n in range(1, len(l)) for a in it.combinations(l, n)]

def get_combinations_for_target(combinations, target):
    if combinations is None:
        return []
    return [combination for combination in combinations if sum(combination) == target]

def get_list_without_used_numbers(l, combination):
    used_numbers = []
    for item in combination:
        used_numbers.append(item)

    diff_list = list(set(l) - set(used_numbers))
    return diff_list

source = [1, 2, 3, 4, 5]
combinations = get_all_combinations(source)
combinations_first =  get_combinations_for_target(combinations, 3)

combinations_both = defaultdict(dict)

for combination in combinations_first:
    partial_list = get_list_without_used_numbers(source, combination)
    partial_combinations = get_all_combinations(partial_list)
    combinations_both[combination] = get_combinations_for_target(partial_combinations, 8)

print(combinations_both)