0

Used the code below to find out the possible combination of a given number. Finding all possible combinations of numbers to reach a given sum

However, if a negative value is in the population, this formula would not work. Is there any amendments that can be made in order to resolve this issue?

Thanks in advance

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

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

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


if __name__ == "__main__":
    subset_sum([-17896,-4774,-1472,701,912,2848,3431,3966], -12284)
Osadhi Virochana
  • 1,294
  • 2
  • 11
  • 21
Adrian Lam
  • 1

1 Answers1

0

at first look: the second check if s >= target: return works only in positive inputs case. When you have negative values in input, the partial sum can be greater than the destination. just disable this check.

sum([-17896, -4774, -1472, 701, 912, 2848, 3431, 3966])=-12284
Sergey Vturin
  • 41
  • 3