How to optimize my code ("How many ways can you make the sum of a number?")

Question

I have a next code (This is the answer to the question "How many ways can you make the sum of a number?"):

import itertools


def exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.extend(set(sorted(itertools.permutations(tup, i))))
    res = [tuple(sorted(q)) for q in res]
    print(len(set(res)))


exp_sum(int(input()))

How to speed up this code several times?

(If input is 11, running time is ~23s)

Answer 1

You do a lot of sorting that is not needed. I give you to functions that perform a lot better.

To compare with input 11:

11.680076 # Your Function
0.10761999999999716 # a better Function keeping the tuples 
0.10596200000000522 # a function don't keep the tuples 

import time
import itertools


t = time.process_time()

elapsed_time = time.process_time() - t

def more_better_exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    counter = 0
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                counter += 1
    print(counter)
        

def better_exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.append(tup)
    print(len(res))
        


        
def exp_sum(n):
    l = [int(i) for i in range(1, n + 1)]
    res = []
    for i in range(1, n + 1):
        for tup in itertools.combinations_with_replacement(l, i):
            if sum(tup) == n:
                res.extend(set(sorted(itertools.permutations(tup, i))))
    res = [tuple(sorted(q)) for q in res]
    print(len(set(res)))

x = int(input())


#YOur Version
t = time.process_time()
exp_sum(x)
print(time.process_time() - t)


# Number and tuples 
t = time.process_time()
better_exp_sum(x)
print(time.process_time() - t)

# Just the number 
t = time.process_time()
more_better_exp_sum(x)
print(time.process_time() - t)