3

I've edited my question as I don't think I've explained it well. The subset_sum function that is linked as a duplicate seems to be when the list of numbers is random but would also work in my situation. However, it seems to be inefficient for large numbers like my function below. My questions is for a list of number that is always known based on the value of N.

If N is 10 the list of numbers would be 1 through 9 or range(1, N). The function should return all unique number combinations from 1 to 9 with a sum of 10. In this case my function below will solve this and return 9 however for large numbers it takes a very long time. It seems to me there should be a better way to solve this when the range of numbers is known than having to iterate through each possible combination. Maybe I'm wrong though.

import itertools

def counter(n):
    count = 0
    l = range(1, n)
    for i in range(1, n):
        for c in itertools.combinations(l, i):
            if sum(c) == n:
                count += 1
    return count
Casey
  • 33
  • 4
  • 5+3+2 is also possible, so it'll return 9. – shiftpsh Jun 08 '17 at 00:22
  • Ah thanks! I thought the function was working properly but couldn't think of the last possibility when I was typing up the question. My question then is really around how this can be made to calculate the solution more efficiently without having to iterate through each possible combination. – Casey Jun 08 '17 at 00:35
  • That's a [Subset sum problem](https://en.wikipedia.org/wiki/Subset_sum_problem) and, although ordered in your case, it still is an NP-complete problem so you cannot solve it by a simple formula. A fellow SO member went to the trouble of writing out the code for solving it: https://stackoverflow.com/a/4633515 – zwer Jun 08 '17 at 00:38
  • 1
    Compute a few, let's say for n in range(10, 20), then throw your sequence into oeis.org – Stefan Pochmann Jun 08 '17 at 00:39
  • @zwer Doesn't look like subset sum at all. – Stefan Pochmann Jun 08 '17 at 00:46
  • The question marked as the duplicate does discuss your point about efficiency, see the part about this problem being NP Hard. – Kelly S. French Jun 12 '17 at 14:54

1 Answers1

0

What you search for is partition function p. Check out https://en.m.wikipedia.org/wiki/Partition_(number_theory) It contains recursive formula which is only linear in terms of input.

enedil
  • 1,605
  • 4
  • 18
  • 34