Im looking for a function that will find all unique combinations from a list that sums up to a number. I cannot afford to go threw all permutations of the list since the lists will be very long and time is of essence.

the_list = [7,6,5,5,4,3,2,1] stop_sum = 11

So if combination (7, 3, 1) is found I don't want (1, 3, 7) to be found.

Currently i'm doing it with a recursive function like down under but it's not enough when the lists contains of 300 numbers. (all integers).

the_list = [7,6,5,5,4,3,2,1]
stop_sum = 11

unique_combos = []
def combo_find(C, S, B=[]):

    for i, a in enumerate(C):

        if a > S:
            continue

        B.append(a) # B [a] can still be a possible list

        if a == S:  # Found a sequence that works

            sequence = sorted(tuple(B))
            if sequence not in unique_combos:
                unique_combos.append(sequence)

        combo_find(C[i   1:], S - a, B)
        B.pop()  # drop [a] from possible list

the_list.sort()
combo_find(the_list, stop_sum)
print(unique_combos)

Anybody have an idea how to do this a smarter/faster way ?

CodePudding user response：

The following should be reasonably performant, using some caching:

from functools import lru_cache

def combo_find(C, S):
    C.sort()

    @lru_cache(None)
    def rec(pool, s):
        if not s:
            return [[]]
        if s < 0:
            return []
        i, result = 0, []
        while i < len(pool):
            crnt = pool[i]
            for combo in rec(pool[i 1:], s-crnt):
                result.append([crnt]   combo)
            # use the first of consecutive equals or none of them!
            # this avoids duplicates, but allows using all occurrences without any membership tests
            while i < len(pool) and pool[i] == crnt:
                i  = 1
        return result

    return rec(tuple(C), S)  # tuplify so the args are hashable

>>> combo_find([7,6,5,5,4,3,2,1], 11)
[[1, 2, 3, 5], [1, 3, 7], [1, 4, 6], [1, 5, 5], [2, 3, 6], [2, 4, 5], [4, 7], [5, 6]]

CodePudding user response：

You can write solve as a function over your numbers, n, and a query sum, q. This algorithm does not require n to be sorted and could be optimized if you make sorting a requirement. The algorithm is written using inductive reasoning -

1. If the query sum q is zero, we already know the answer. Yield the empty solution {} and return.
2. (inductive) q is not zero. If q is negative or n has no numbers left to check, then the solution is out-of-bounds or could not be reached. Return.
3. (inductive) q is positive and n has at least one number to check. For each solution of the sub-problem, add the first n if it does not already exist in the solution, then yield. Additionally attempt to solve the same query q by skipping the first n.

def solve (n, q):
  # 1. solution found, return empty set
  if q == 0: return (yield set())
  # 2. solution out of bounds or no more nums to check
  if q < 0 or not n: return
  # 3. for each solution to sub-problem, if first n not in solution, add it
  for sln in solve(n[1:], q - n[0]):
    if n[0] not in sln:
      yield {n[0], *sln}
  # 3. and solve q skipping the first n
  yield from solve(n[1:], q)

the_list = [7,6,5,5,4,3,2,1]

for x in solve(the_list, 11):
  print(x)

{4, 7}
{1, 3, 7}
{5, 6}
{5, 6}
{1, 4, 6}
{2, 3, 6}
{2, 4, 5}
{1, 2, 3, 5}
{2, 4, 5}
{1, 2, 3, 5}

n can be any order -

the_list = [2,1,5,3]

for x in solve(the_list, 8):
  print(x)

{1, 2, 5}
{3, 5}

If a solution cannot be found, you will get an empty result -

print(list(solve([1,2,3], 99)))

[]