Найти колличество вариантов сумм числа n

[Igor_Korneev]

Помогите, пожалуйста решить: Задано целое положительное число n. Сколько существует способов пред-ставить его в виде суммы различных целых положительных слагаемых? Спо-собы, отличающиеся только порядком слагаемых, считаются одинаковыми.
Поскольку ответ может быть очень большим, найдите остаток от деления искомого количества на простое число 998 244 353.
Пример:
Ввод: 10
Вывод: 10
Пояснение:
10 = 1 + 2 + 3 + 4, 10 = 1 + 2 + 7, 10 = 1 + 3 + 6, 10 = 1 + 4 + 5, 10 = 1 + 9, 10 = 2 + 3 + 5, 10 = 2 + 8, 10 = 3 + 7, 10 = 4 + 6, 10 = 10
Пример 2:
Ввод: 5
Вывод: 3
Пояснение:
5 = 1 + 4, 5 = 2 + 3, 5 = 5

[Дмитрий Филюшкин]

Здравствуйте, Игорь.
Вот решение для Вас:

n = int(input("Ввод: "))
# В sums я храню список, в котором списки чисел. Эти списки - они слагаемые,
# сумма которых - заданное число n
sums = list()
# Запускаю цикл для перебора вариантов. Здесь число i я представляю в двоичной
# форме. И эту форму преобразую к списку чисел. Например, так
# i = 27
# В двоичной форме это 11011. Это число я преобразую к списку [1, 2, 4, 5].
# Или так:
# i = 28
# В двоичной форме это 11100. От этого числа я получаю список [3, 4, 5]. То
# есть числа списка - это позиции, на которых стоят единицы в двоичной форме i.
# И так я перебираю i от единицы до 2 в степени n. Плюс в задании стоит
# ограничение - перебирать не более 998 244 353 чисел
count = 2**n
if count > 998244353:
    count = 998244353
for i in range(1, count):
    # Создаю список для чисел
    s = []
    # Сохраняю значение "i", чтобы с ним работать
    k = i
    # Сначала я анализирую первую единицу в двоичной записи числа "k"
    d = 1
    # Запускаю цикл для трансформирования числа "k" в список "s"
    while k > 0:
        # Если k - нечётное, тогда добавляю в список номер этой единицы
        if k % 2 == 1:
            s.append(d)
        # Увеличиваю номер анализируемой единицы
        d += 1
        # Сдвигаю число k вправо в двоичной форме
        k = k // 2
    # Проверяю, что сумма чисел списка равна нашему числу "n"
    if sum(s) == n:
        # Добавляю найденную сумму в список сумм
        sums.append(s)

# Вывожу длину списка сумм - это количество, то, сколькими разными способами
# можно получить число "n"
print("Вывод:",len(sums))
print("Пояснение:")
for i in sums:
    print(n, "=", end = " ")
    print(*i, sep = " + ", end = "; ")

[BDA]

Дмитрий Филюшкин, мне кажется, так нельзя ограничивать перебор. Перебирать нужно все варианты, а только при выводе ответа делать:

print("Вывод:", len(sums) % 998244353)

Еще можно сократить перебор, отдельно считая случай, когда число равно самому себе:

for i in range(1, 2**(n - 1)):
...
sums.append([n])

[BDA]

Некоторые оптимизации:

from itertools import combinations
import timeit

def f1(n):
    sums = list()
    for i in range(1, 2**n):
        s = []
        k = i
        d = 1
        while k > 0:
            if k % 2 == 1:
                s.append(d)
            d += 1
            k = k // 2
        if sum(s) == n:
            sums.append(s)
    return sums

def f2(n):
    sums = list()
    for i in range(1, 2**(n - 1)):
        s = []
        k = i
        d = 1
        while k > 0:
            if k % 2 == 1:
                s.append(d)
            d += 1
            k = k // 2
        if sum(s) == n:
            sums.append(s)
    sums.append([n])
    return sums

def f3(n):
    nums = list(range(1, n + 1))
    sums = list()
    for i in nums:
        for j in combinations(nums, i):
            if sum(j) == n:
                sums.append(j)
    return sums

def f3t(n):
    nums = list(range(1, n + 1))
    return [j for i in nums for j in combinations(nums, i) if sum(j) == n]

def f4(n):
    nums = list(range(1, n + 1))
    sums = list()
    k = 0
    for i in nums:
        k += i
        if k > n:
            break
        for j in combinations(nums, i):
            if sum(j) == n:
                sums.append(j)
    return sums

for f in ['f1(20)', 'f2(20)', 'f2(21)', 'f3(21)', 'f3(24)', 'f4(24)', 'f4(35)']:
    print(f, timeit.timeit(stmt = f, globals = globals(), number = 1))

f1 - решение Дмитрия (без ограничения count). f2 - вынесение случая из цикла, когда число равно самому себе. f3 - отказ от ручного преобразования битовой маски в список чисел (пусть питон сам сгенерирует все комбинации заданной длины). f3t - более краткий способ записи f3 (на основе list comprehension). f4 - ограничение на количество слагаемых (большее количество слагаемых даст сумму, точно превышающую число). Замеры:

f1(20) 3.900752850558896
f2(20) 1.8287467453846484
f2(21) 3.8289950810629483
f3(21) 0.5194538556796697
f3(24) 4.5272020821362595
f4(24) 0.03785458413099363
f4(35) 1.7937140414664388

Грубо говоря, получили ускорение в 700 раз, но, кажется, это тупиковый путь, так как ответ 585 функцией f4 найден за примерно 1.8 секунды, что крайне далеко от числа-ограничителя 998244353

UPD. Еще вариант (вместо питоновских combinations рекурсия):

def f5(n):
    sums = list()

    def f(sum_, used_nums, last_i):
        for i in range(last_i + 1, n + 1):
            new_sum = sum_ + i
            if new_sum < n:
                used_nums.add(i)
                f(new_sum, used_nums, i)
                used_nums.discard(i)
            elif new_sum == n:
                sums.append(sorted(list(used_nums) + [i]))
            else:
                break

    f(0, set(), 0)
    return sums

def f5t(n):
    def f(sum_, last_i):
        r = 0
        for i in range(last_i + 1, n + 1):
            new_sum = sum_ + i
            if new_sum < n:
                r += f(new_sum, i)
            elif new_sum == n:
                return r + 1
            else:
                return r
    return f(0, 0)

f1(20) 4.251371658614067
f2(20) 1.9784875386331882
f2(21) 4.219702216906908
f3(21) 0.5704587337384197
f3(24) 4.774702565649914
f4(24) 0.03959370034723442
f4(35) 2.0411703253171822
f5(35) 0.0031282119805631226
f5(100) 3.969237034616512
f5t(100) 2.747479150150344

f5t - отказ от построения списка вариантов, а только поиск количества вариантов (в задаче сам список не просят). Но f5(100) = 444793 все еще далек от 998244353.