Introduction

In this problem, we are asked to find two disjoint subsets of an array such that both subsets have the same sum.

The key constraints are: - $$$3 \le n \le 40$$$ - $$$\sum_{i=1}^{n} x_i \le 2^{n} - 2$$$

After solving it on my own, I looked through several other submissions but couldn’t find an approach similar to mine. I found my solution quite elegant, so I decided to share it here.

Prerequisites

• Pigeonhole Principle
• Fast Fourier Transform (FFT)
• Meet in the middle

Observation 1

It is sufficient to find two distinct subsets $$$A$$$ and $$$B$$$ such that

Indeed, let

Then $$$A'$$$ and $$$B'$$$ are disjoint, and

Therefore, any two distinct subsets with equal sum can be transformed into two disjoint subsets with equal sum.

Observation 2

The total number of non empty subsets is $$$2^{n}-1$$$.

On the other hand, since

the number of possible subset sums is at most $$$2^{n}-2$$$.

Hence, there are more subsets than possible sums, so by the Pigeonhole Principle, there exist two distinct subsets with the same sum. By observation 1, this implies that a valid solution always exists.

Finding the Collision

The remaining task is to efficiently find two subsets with equal sum.

To achieve this, we use a meet in the middle approach. We split the array into two halves, say $$$L$$$ and $$$R$$$, each of size at most $$$20$$$.

For each half, we construct a polynomial where the coefficient of $$$x^s$$$ represents the number of subsets with sum $$$s$$$. Formally, for a set $$$S$$$, define

We compute $$$P_L(x)$$$ and $$$P_R(x)$$$, and then multiply them:

The coefficient of $$$x^k$$$ in $$$P(x)$$$ represents the number of subsets of the full array whose sum is $$$k$$$. Using Fast Fourier Transform (FFT), this multiplication can be done efficiently.

A collision (i.e., a sum $$$k$$$ with coefficient at least $$$2$$$) guarantees the existence of two distinct subsets with the same sum, which, by Theorem 1, yields two disjoint subsets with equal sum.

Polynomial Compression

A direct construction of the polynomial is still too large, since the maximum possible sum can be as large as $$$10^{12}$$$, making the degree of the polynomial infeasible.

To address this, we compress the polynomial by working modulo $$$x^k$$$ for a suitably chosen integer $$$k$$$. That is, instead of tracking exact sums, we only track them modulo $$$k$$$:

This effectively reduces the degree of the polynomial to at most $$$k$$$, allowing us to perform all computations efficiently using FFT.

Although this introduces collisions between different sums that are congruent modulo $$$k$$$, this is acceptable: we are only interested in finding any collision. Once a collision is detected modulo $$$k$$$, we can recover the actual subsets and verify that their sums are equal.

By choosing $$$k$$$ appropriately, we ensure a high probability (or guarantee, depending on bounds) of detecting a valid collision while keeping the computation tractable.

Recovering the Answer

Finally, we explain how to recover an explicit solution from the compressed polynomial.

After computing the polynomial modulo $$$x^k - 1$$$, each coefficient represents the number of subsets whose sum is congruent to a given value modulo $$$k$$$. That is, for each residue $$$r$$$, we know how many subsets satisfy

By the Pigeonhole Principle, since the total number of subsets is large compared to $$$k$$$, there must exist a residue $$$r$$$ whose coefficient exceeds the expected average. In particular, there exists some $$$r$$$ such that multiple distinct subsets map to it.

We then focus on this residue class and explicitly enumerate subsets (typically via meet-in-the-middle) whose sums are congruent to $$$r \pmod{k}$$$, until we find two distinct subsets with the same exact sum.

Once such a pair is found, we apply Theorem 1 to transform them into two disjoint subsets with equal sum.