How to return all unique combinations of numbers with sum N

I edited my question as I don't think I 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, for large numbers like my function, this is inefficient. My questions is a list of numbers that is always known based on the value of N.

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

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

      

+3


source to share


1 answer


What you are looking for is the p section function. Check out https://en.m.wikipedia.org/wiki/Partition_(number_theory) It contains a recursive formula that is only linear in terms of input.



0


source







All Articles