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)

CodePudding user response：

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 -

1. (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

2. (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.

3. (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.

CodePudding user response：

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