仅查找具有指定值的一个子集总和

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

递归函数在实际应用中很麻烦，因为方法调用的每个实例都需要由解释器跟踪。如果可能，请在循环中编写您的函数，而不是递归调用它。

这是一种算法，它反复尝试添加输入中低于剩余值的最大值。如果失败，它会删除尝试过的最大值并从头开始。它将 return 它找到的第一个解决方案。在一组 10,000 个值中大约需要 8 秒。

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

仅查找具有指定值的一个子集总和

Find only one subset sum with a specified value

python

algorithm

dynamic-programming

combinatorics

subset-sum