Найти только одну сумму подмножества с указанным значением

Question

Не печатать все подмножества с указанной суммой, но только с одной и с наименьшей временной сложностью.

found = False


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

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

    if found:
        return

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

Проблема в том, что слишком большие данные для больших данных (10000 элементов).

Answer 1

Рекурсивные функции создают проблемы в реальных приложениях, поскольку интерпретатор должен отслеживать каждый экземпляр вызова метода. Если возможно, напишите свою функцию в al oop, а не вызывайте ее рекурсивно.

Вот алгоритм, который неоднократно пытается добавить наибольшее значение на входе ниже, чем оставшееся значение. Если это не удается, он удаляет наибольшее значение и запускается с начала. Он вернет первое найденное решение. Занимает около 8 секунд при наборе 10000 значений.

def one_subset_sum(sum_val: int, set_ints: list):
  test_subset = []
  filtered_ints = list(filter(lambda x:x<=sum_val,set_ints))
  while sum(test_subset) < sum_val and len(set_ints) > 0:
    remainder = sum_val - sum(test_subset)
    filtered_ints = list(filter(lambda x:x<=remainder,filtered_ints))
    if len(filtered_ints) == 0:
        set_ints.remove(max(set_ints))
        test_subset = []
        filtered_ints = list(filter(lambda x:x<=sum_val,set_ints))
        if sum(set_ints) < sum_val:
            return []
        continue
    test_subset.append(max(filtered_ints))
    filtered_ints.remove(test_subset[-1])
  return test_subset