How do i optimize this code to run for larger values?

Question

I'm writing a python function that takes an integer value between 3 and 200 as input, calculates the number of sums using unique nonzero numbers that will equal the number and prints the output. For example; with 3 as input 1 will be printed because only 1 + 2 will give 3, with 6 as input 3 will be printed because 1+2+3, 1+5 and 2+4 equal 6. My code works well only for numbers less than 30 after which it starts getting slow. How do I optimize my code to run efficiently for all input between 3 and 200.

from itertools import combinations

def solution(n):
    count = 0
    
    max_terms = 0
    num = 0
    for i in range(1,n):
        if num + i <= n:
            max_terms += 1
            num = num + i

    for terms in range(2,max_terms + 1):
        for sample in list(combinations(list(range(1,n)),terms)):
            if sum(sample) == n:
                count += 1

    print(count)

First, don't generate all combinations of number and filter them afterwards: only generate the valid ones. For even larger numbers, this becomes a maths problem: don't generate combinations, just count how many of them there can be. — Thierry Lathuille, Dec 12 '21 at 07:38
These are just partitions, right? https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning — Larry the Llama, Dec 12 '21 at 07:47
You mean "unique *positive* numbers"? "Nonzero" numbers would allow negative numbers, which would allow for an infinite number of sums to any target value. — RBarryYoung, Dec 12 '21 at 14:45

score 2 · Accepted Answer · answered Dec 12 '21 at 08:55

Generating all combinations is indeed not very efficient as most will not add up to n.

Instead, you could use a recursive function, which can be called after taking away one partition (i.e. one term of the sum), and will solve the problem for the remaining amount, given an extra indication that future partitions should be greater than the one just taken.

To further improve the efficiency, you can use memoization (dynamic programming) to avoid solving the same sub problem multiple times.

Here is the code for that:

def solution(n, least=1, memo={}):
    if n < least:
        return 0
    key = (n, least)
    if key in memo:  # Use memoization
        return memo[key]
    # Counting the case where n is not partitioned
    #    (But do not count it when it is the original number itself)
    count = int(least > 1)
    # Counting the cases where n is partitioned
    for i in range(least, (n + 1) // 2):
        count += solution(n - i, i + 1)
    memo[key] = count
    return count

Tested the code with these arguments. The comments list the sums that are counted:

print(solution(1)) # none
print(solution(2)) # none
print(solution(3)) # 1+2
print(solution(4)) # 1+3
print(solution(5)) # 1+4, 2+3
print(solution(6)) # 1+2+3, 1+5, 2+4
print(solution(7)) # 1+2+4, 1+6, 2+5, 3+4
print(solution(8)) # 1+2+5, 1+3+4, 1+7, 2+6, 3+5
print(solution(9)) # 1+2+6, 1+3+5, 2+3+4, 1+8, 2+7, 3+6, 4+5
print(solution(10)) # 1+2+3+4, 1+2+7, 1+3+6, 1+4+5, 2+3+5, 1+9, 2+8, 3+7, 4+6

score 0 · Answer 2 · answered Dec 12 '21 at 08:10

your question isn't clear enough. So, I'm making some assumptionns...

So, what you want is to enter a number. say 4 and then, figure out the total combinations where two different digits add up to that number. If that is what you want, then the answer is quite simple.

for 4, lets take that as 'n'. 'n' has the combinations 1+3,2+2.

for n as 6, the combos are - 1+5,2+4,3+3.

You might have caught a pattern. (4 and 6 have half their combinations) also, for odd numbers, they have combinations that are half their previous even number. i.e. - 5 has (4/2)=2 combos. i.e. 1+4,2+3 so...

the formula to get the number for comnbinations are -

(n)/2 - this is if you want to include same number combos like 2+2 for 4 but, exclude combos with 0. i.e. 0+4 for 4
(n+1)/2 - this works if you want to exclude either the combos with 0 i.e. 0+4 for 4 or the ones with same numbers i.e. 2+2 for 4.
(n-1)/2 - here, same number combos are excluded. i.e. 2+2 wont be counted as a combo for n as 4. also, 0 combos i.e. 0+4 for 4 are excluded.

n is the main number. in these examples, it is '4'. This will work only if n is an integer and these values after calculations are stored as an integer. 3 number combos are totally different. I'm sure there's a formula for that too.

You would need to have a formula for generating 3 terms, 4 terms, 5 terms, 6 terms, ...etc. There is really no end to that. So it does not help to only have formulas for specific number of partitions. A more generic solution is needed which tackles them all. — trincot, Dec 12 '21 at 09:00

How do i optimize this code to run for larger values?

2 Answers2