Determine which numbers in list add up to specified value
Question: I have a quick (hopefully accounting problem. I just entered a new job and the
books are a bit of a mess. The books have these lump sums logged, while the
bank account lists each and every individual deposit. I need to determine
which deposits belong to each lump sum in the books. So, I have these four
lump sums:

[6884.41, 14382.14, 2988.11, 8501.60]

I then have this larger list of individual deposits (sorted):

[98.56, 98.56, 98.56, 129.44, 160.0, 242.19, 286.87, 290.0, 351.01, 665.0,
675.0, 675.0, 677.45, 677.45, 695.0, 695.0, 695.0, 695.0, 715.0, 720.0, 725.0,
730.0, 745.0, 745.0, 750.0, 750.0, 750.0, 750.0, 758.93, 758.93, 763.85,
765.0, 780.0, 781.34, 781.7, 813.79, 824.97, 827.05, 856.28, 874.08, 874.44,
1498.11, 1580.0, 1600.0, 1600.0]

In Python, how can I determine which sub-set of the longer list sums to one of
the lump sum values? (NOTE: these numbers have the additional problem that the
sum of the lump sums is $732.70 more than the sum of the individual accounts.
I'm hoping that this doesn't make this problem completely unsolvable)


Answer: Here's a pretty good start at a solution:

    
    
    import datetime as dt
    from itertools import groupby
    from math import ceil
    
    def _unique_subsets_which_sum_to(target, value_counts, max_sums, index):
        value, count = value_counts[index]
        if index:
            # more values to be considered; solve recursively
            index -= 1
            rem = max_sums[index]
    
            # find the minimum amount that this value must provide,
            # and the minimum occurrences that will satisfy that value
            if target <= rem:
                min_k = 0
            else:
                min_k = (target - rem + value - 1) // value  # rounded up to next int
    
            # find the maximum occurrences of this value
            # which result in <= target
            max_k = min(count, target // value)
    
            # iterate across min..max occurrences
            for k in range(min_k, max_k+1):
                new_target = target - k*value
                if new_target:
                    # recurse
                    for solution in _unique_subsets_which_sum_to(new_target, value_counts, max_sums, index):
                        yield ((solution + [(value, k)]) if k else solution)
                else:
                    # perfect solution, no need to recurse further
                    yield [(value, k)]
        else:
            # this must finish the solution
            if target % value == 0:
                yield [(value, target // value)]
    
    def find_subsets_which_sum_to(target, values):
        """
        Find all unique subsets of values which sum to target
    
            target   integer >= 0, total to be summed to
            values   sequence of integer > 0, possible components of sum
        """
        # this function is basically a shell which prepares
        #  the input values for the recursive solution
    
        # turn sequence into sorted list
        values = sorted(values)
        value_sum = sum(values)
    
        if value_sum >= target:
            # count how many times each value appears
            value_counts = [(value, len(list(it))) for value,it in groupby(values)]
    
            # running total to each position
            total = 0
            max_sums = [0]
            for val,num in value_counts:
                total += val * num
                max_sums.append(total)
    
            start = dt.datetime.utcnow()
            for sol in _unique_subsets_which_sum_to(target, value_counts, max_sums, len(value_counts) - 1):
                yield sol
            end = dt.datetime.utcnow()
            elapsed = end - start
            seconds = elapsed.days * 86400 + elapsed.seconds + elapsed.microseconds * 0.000001
            print("  -> took {:0.1f} seconds.".format(seconds))
    
    # I multiplied each value by 100 so that we can operate on integers
    # instead of floating-point; this will eliminate any rounding errors.
    values = [
        9856, 9856, 9856, 12944, 16000, 24219, 28687, 29000, 35101, 66500,
        67500, 67500, 67745, 67745, 69500, 69500, 69500, 69500, 71500, 72000,
        72500, 73000, 74500, 74500, 75000, 75000, 75000, 75000, 75893, 75893,
        76385, 76500, 78000, 78134, 78170, 81379, 82497, 82705, 85628, 87408,
        87444, 149811, 158000, 160000, 160000
    ]
    sum_to = [
        298811,
        688441,
        850160  #,
                # 1438214
    ]
    
    def main():
        subset_sums_to = []
        for target in sum_to:
            print("\nSolutions which sum to {}".format(target))
            res = list(find_subsets_which_sum_to(target, values))
            print("  {} solutions found".format(len(res)))
            subset_sums_to.append(res)
        return subset_sums_to
    
    if __name__=="__main__":
        subsetsA, subsetsB, subsetsC = main()
    

which on my machine results in

    
    
    Solutions which sum to 298811
      -> took 0.1 seconds.
      2 solutions found
    
    Solutions which sum to 688441
      -> took 89.8 seconds.
      1727 solutions found
    
    Solutions which sum to 850160
      -> took 454.0 seconds.
      6578 solutions found
    
    # Solutions which sum to 1438214
    #   -> took 7225.2 seconds.
    #   87215 solutions found
    

The next step is to cross-compare solution subsets and see which ones can
coexist together. I think the fastest approach would be to store subsets for
the smallest three lump sums, iterate through them and (for compatible
combinations) find the remaining values and plug them into the solver for the
last lump sum.

* * *

Continuing from where I left off (+ a few changes to the above code to grab
the return lists for subsums to the first three values).

I wanted a way to easily get the remaining value-coefficients each time;

    
    
    class NoNegativesDict(dict):
        def __sub__(self, other):
            if set(other) - set(self):
                raise ValueError
            else:
                res = NoNegativesDict()
                for key,sv in self.iteritems():
                    ov = other.get(key, 0)
                    if sv < ov:
                        raise ValueError
                    # elif sv == ov:
                    #     pass
                    elif sv > ov:
                        res[key] = sv - ov
                return res
    

then I apply it as

    
    
    value_counts = [(value, len(list(it))) for value,it in groupby(values)]
    vc = NoNegativesDict(value_counts)
    nna = [NoNegativesDict(a) for a in subsetsA]
    nnb = [NoNegativesDict(b) for b in subsetsB]
    nnc = [NoNegativesDict(c) for c in subsetsC]
    
    # this is kind of ugly; with some more effort
    # I could probably make it a recursive call also
    b_tries = 0
    c_tries = 0
    sol_count = 0
    start = dt.datetime.utcnow()
    
    for a in nna:
        try:
            res_a = vc - a
            sa = str(a)
    
            for b in nnb:
                try:
                    res_b = res_a - b
                    b_tries += 1
                    sb = str(b)
    
                    for c in nnc:
                        try:
                            res_c = res_b - c
                            c_tries += 1
    
                            #unpack remaining values
                            res_values = [val for val,num in res_c.items() for i in range(num)]
                            for sol in find_subsets_which_sum_to(1438214, res_values):
                                sol_count += 1
                                print("\n================")
                                print("a =", sa)
                                print("b =", sb)
                                print("c =", str(c))
                                print("d =", str(sol))
    
                        except ValueError:
                            pass
    
                except ValueError:
                    pass
    
        except ValueError:
            pass
    
    print("{} solutions found in {} b-tries and {} c-tries".format(sol_count, b_tries, c_tries))
    end = dt.datetime.utcnow()
    elapsed = end - start
    seconds = elapsed.days * 86400 + elapsed.seconds + elapsed.microseconds * 0.000001
    print("  -> took {:0.1f} seconds.".format(seconds))
    

and the final output:

    
    
    0 solutions found in 1678 b-tries and 93098 c-tries
      -> took 73.0 seconds.
    

So the final answer is **there is no solution for your given data**.

Hope that helps ;-)

