4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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\}$. $\endgroup$ – Yuval Filmus Feb 8 '18 at 12:14
  • $\begingroup$ @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. $\endgroup$ – orlp Feb 8 '18 at 12:19
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.