Search code examples
pythonlistfunctionsumfinance

How can I write a function that finds any and all elements of a list that add to a target?


I have been hired to reconcile years of financial records that have quite large discrepancies. The statements are listed in excel and include a name and figure of the transaction (either positive or negative for credit/debit). I've been asked to manually read through all the statements to find any combination of values that would add to the discrepancy, but there's thousands of lines and I figured a program that could operate immediately for each financial year would be much more appropriate.

As an example, if I have a list [1,3,6,7,10] and my target was 14, I would hope for an output like [(1,6,7), (1,3,10)].

I have seen many questions asked where they try to find pairs of solutions, but I was hoping to expand that to find n solutions.

I've tried using excel's solver tool but it's limited to only 200 variables. I've tried writing a function that iterates through the list but I only have an elementary understanding of python and this feels beyond my reach. If anyone has any ideas as to the process I could take I would really appreciate it, cheers.


Solution

  • You could use recursion to try all subsequences of the list.

    def findSums(l, target):
        res = []
        def go(curr, i, s):
            if s == target:
                res.append(tuple(curr))
            elif s < target and i < len(l):
                go(curr + [l[i]], i + 1, s + l[i])
                go(curr, i + 1, s)
        go([], 0, 0)
        return res
    

    Alternatively, you could use itertools.combinations.

    def findSums(l, target):
        from itertools import combinations
        return [tuple(x) for i in range(1, len(l) + 1) for x in combinations(l, i) 
                         if sum(x) == target]