Встреча посередине

Сколько существует наборов чисел из списка — возможно, пустых, — сумма которых равна $s$?

Здесь чисел до 34, и $2^{34}$ вариантов перебрать нельзя. Но можно перебрать половину.

В первой строке числа $n$ от $1$ до $34$ и $s$ от $0$ до $4 \cdot 10^{10}$. Во второй — $n$ чисел от $1$ до $10^9$.

Одно число.

Разбейте список пополам и переберите все наборы в каждой половине отдельно — это по $2^{17}$ вариантов. Затем для каждой суммы правой половины посчитайте, сколько сумм левой дополняют её до $s$. Словарь подсчётов делает это мгновенно.