Две равные кучки

Сколькими способами можно разложить все числа списка на две непустые кучки с равными суммами? Кучки различаются составом, а разложения, отличающиеся только тем, какая кучка первая, считаются одним.

В первой строке число $n$ от $2$ до $18$. Во второй — $n$ чисел от $1$ до $10^9$.

Одно число.

Каждое разложение встретится в переборе дважды — как «набор» и как «его дополнение».