Как найти количество вариантов получения числа из последовательности чисел? Дана последовательность чисел. Например: 2 9 3 6 3 8 1 10 6 7.
Нужно узнать: сколькими способами можно образовать число, большее 8. При чем есть важное условие: если мы уже добились того, что комбинация больше 8 (3+3+3=9), то дополнять комбинацию новыми числами уже нельзя (3+3+3+5 - нельзя, ведь 3+3+3 - уже > 8).
Правильные ответ - 42, но я никак не могу понять как его добиться.
Я понимаю, что можно перебирать последовательность (2+9, 2+3+3, 2+...) и смотреть, больше 8 или нет, но это слишком долго. Я гуглил уже комбинаторику, но вот не нашел решение. Поэтому обратился сюда.
Подскажите формулу или толкните в нужном направлении.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно воспользоваться динамическим программированием. Введем массив dp, где dp[i] будет означать количество способов получить число i. Изначально dp[0] = 1 (один способ получить число 0 - не брать ни одного числа).

Затем пройдем по всей последовательности чисел и для каждого числа num обновим массив dp. Для этого будем перебирать все числа от 8 до num и прибавлять количество способов из dp[i - num]. Единственное условие - значение dp[i] не должно быть уже больше 0 (т.е. комбинация чисел, образующая число i, не должна быть уже найдена ранее).

После прохода по всей последовательности суммируем значения dp[i] для всех i от 9 до суммы всех чисел в последовательности.

Вот пример кода на Python:

nums = [2, 9, 3, 6, 3, 8, 1, 10, 6, 7]
dp = [0] * (sum(nums) + 1)
dp[0] = 1
for num in nums:
for i in range(sum(nums), num - 1, -1):
if dp[i - num] > 0:
dp[i] += dp[i - num]
result = sum(dp[9:])
print(result)

Этот код позволит найти количество способов образовать число, большее 8, используя числа из заданной последовательности. В вашем случае правильный ответ - 42.