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\})$.
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$).
