# Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

I am trying to think of how to optimize the following problem:

Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I have implemented an algorithm that checks all partitions of $S$ into 2 subsets $P_1$ and $P_2$, but I am wondering if there is a faster algorithm.

Hint: find a recurrence $f(n, k)$ that tells you in how many different ways you can sum to $k$ using the first $n$ integers (ignoring order and using numbers at most once). Then the answer to your problem is $\frac 1 2 f(n, n(n+1)/4)$.
The trick is to realize that the sum of $P$, is $S= \displaystyle \sum_{k=1}^n = \frac{1}{2}n(n+1)$, and that if you partition a set in two with equal sums, both halves must sum to $\frac{1}{2}P$. After counting the number of ways to sum to $\frac{1}{2}P$ we must still divide by two due to order, as for example the partition $(\{3\}, \{1, 2\})$ is the same as $(\{1, 2\}, \{3\})$.
• Actually the partition $(\{3\},\{1,2\})$ is not the same as the partition $(\{1,2\},\{3\})$, since the first one has $P_1 = \{3\}$, and the second one has $P_1 = \{1,2\}$. Feb 8, 2018 at 12:14
• @YuvalFilmus Well it depends on if you can distinguish $P_1$ or $P_2$ or not. Either way it's just a factor of $\frac{1}{2}$, and it's up to OP to decide what he/she wants.
This is A058377, possibly up to a normalization by 2. Since the sum of $P_1$ has to equal $n(n-1)/4$, the number of solutions is zero when $n \equiv 1,2 \pmod{4}$ (since $n(n-1)/2$ is odd for such values of $n$).