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) / Number Theoretic Transform (NTT)
- Meet in the Middle
Observation 1
It is sufficient to find two distinct subsets $$$A$$$ and $$$B$$$ (not necessarily disjoint) satisfying $$$\sum_{x \in A} x = \sum_{x \in B} x$$$.
Intuition. If $$$A$$$ and $$$B$$$ share elements, those elements contribute equally to both sums and can simply be cancelled out. What remains on each side is a pair of disjoint subsets with equal sum.
Proof. Define $$$A' = A \setminus B$$$ and $$$B' = B \setminus A$$$. By construction $$$A' \cap B' = \emptyset$$$. Since $$$A \neq B$$$, it is impossible that both $$$A' = \emptyset$$$ and $$$B' = \emptyset$$$, so at least one is nonempty. Furthermore, cancelling the shared part $$$A \cap B$$$:
We claim neither $$$A'$$$ nor $$$B'$$$ can be empty. If $$$A' = \emptyset$$$, then $$$\sum_{x \in A} x = \sum_{x \in A \cap B} x$$$, so $$$\sum_{x \in B'} x = 0$$$. Since all elements are positive, $$$B' = \emptyset$$$ as well — contradicting $$$A \neq B$$$. By symmetry the same holds for $$$B'$$$.
Therefore $$$A'$$$ and $$$B'$$$ are two nonempty disjoint subsets with equal sum. $$$\blacksquare$$$
Observation 2 (Existence)
A valid solution always exists under the given constraints.
Proof. The number of nonempty subsets of the array is $$$2^n - 1$$$. Each subset has a sum in the range $$$\left[1,\, \sum_{i=1}^n x_i\right] \subseteq \left[1,\, 2^n - 2\right]$$$, so there are at most $$$2^n - 2$$$ distinct possible sums.
Since $$$2^n - 1 \gt 2^n - 2$$$, by the Pigeonhole Principle two distinct nonempty subsets must share the same sum. Observation 1 then guarantees the existence of two nonempty disjoint subsets with equal sum. $$$\blacksquare$$$
Finding the Collision via Meet in the Middle
Existence is guaranteed; we now need to find the two subsets efficiently.
The naive approach would be to enumerate all $$$2^n$$$ subsets, record their sums, and look for a duplicate. For $$$n = 40$$$ this is $$$2^{40} \approx 10^{12}$$$ subsets — far too slow.
Meet in the middle cuts this in half. Split the array into two halves $$$L$$$ and $$$R$$$, each of size at most $$$\lceil n/2 \rceil \le 20$$$. Now we only enumerate $$$2^{20} \approx 10^6$$$ subsets per half. The idea is to express any subset of the full array as a union $$$T_L \cup T_R$$$ with $$$T_L \subseteq L$$$ and $$$T_R \subseteq R$$$, so its sum is $$$\sum T_L + \sum T_R$$$.
A natural way to count subsets by sum is via generating polynomials. For a set $$$S$$$, define:
The coefficient of $$$x^k$$$ in $$$P_S(x)$$$ equals the number of subsets of $$$S$$$ whose elements sum to $$$k$$$. For example, if $$$S = {2, 3}$$$, then $$$P_S(x) = 1 + x^2 + x^3 + x^5$$$ (corresponding to subsets $$$\emptyset, {2}, {3}, {2,3}$$$).
Now observe that since every full-array subset splits as $$$T_L \cup T_R$$$:
because when we multiply $$$P_L$$$ and $$$P_R$$$, the coefficient of $$$x^k$$$ in the product counts exactly the pairs $$$(T_L, T_R)$$$ with $$$\sum T_L + \sum T_R = k$$$ — i.e., all subsets of the full array summing to $$$k$$$. A coefficient of $$$2$$$ or more at any $$$x^k$$$ certifies that two distinct such subsets exist, giving us our collision.
This multiplication is carried out via NTT in $$$O(M \log M)$$$ time, where $$$M$$$ is the degree of the product polynomial.
Polynomial Compression
The maximum possible subset sum is $$$\sum x_i \le 2^n - 2 \approx 10^{12}$$$ for $$$n = 40$$$, making the degree of $$$P(x)$$$ completely infeasible to handle directly.
The key idea: we don't need to track exact sums at all — we only need to find a residue class that is overcrowded, and then search within it for a collision. So instead of computing $$$P(x)$$$ exactly, we truncate it: we compute $$$P(x) \bmod x^k$$$ for a suitably chosen integer $$$k$$$.
Concretely, define the compressed polynomial of a set $$$S$$$ as:
In other words, we simply ignore all terms of degree $$$\ge k$$$, which is equivalent to only recording each subset sum modulo $$$k$$$. The coefficient of $$$x^r$$$ tells us how many subsets of $$$S$$$ have sum with remainder $$$r$$$ when divided by $$$k$$$.
Why does truncation work here, and not cyclic reduction? If we reduced modulo $$$x^k - 1$$$ (cyclic), the coefficient of $$$x^r$$$ in the product would count pairs where $$$(\sum T_L + \sum T_R) \equiv r \pmod k$$$, which is the same information. The difference is purely implementation: truncating at $$$x^k$$$ is equivalent to zeroing out high-degree terms after the ordinary (acyclic) convolution, while cyclic reduction would require a negacyclic NTT. Since we perform an ordinary NTT and then fold the result (see the "Detecting a Useful Residue Class" section), truncation is the natural framing.
Now, $$$\tilde{P}_L(x) \cdot \tilde{P}_R(x) \bmod x^k$$$ has degree at most $$$k - 1$$$, so we can compute it with an NTT on arrays of size $$$O(k)$$$ in $$$O(k \log k)$$$ time. The coefficient of $$$x^r$$$ in this product counts pairs $$$(T_L, T_R)$$$ with $$$T_L \subseteq L$$$, $$$T_R \subseteq R$$$, and $$$(\sum T_L + \sum T_R) \bmod k = r$$$.
Choosing $$$k$$$. We set $$$k \approx 2 \cdot 10^5$$$. The number of subsets of the full array is $$$2^n$$$, so the average count per residue class is $$$2^n / k$$$. For $$$n = 40$$$, this is roughly $$$2^{40} / (2 \cdot 10^5) \approx 5 \cdot 10^6$$$. Meanwhile the number of distinct exact sums in any residue class is at most $$$\lfloor (\sum x_i) / k \rfloor + 1 \approx (2^{40}) / (2 \cdot 10^5) \approx 5 \cdot 10^6$$$ as well — so at worst these quantities are comparable. For smaller $$$n$$$ the ratio is much more favorable. The point is that by the Pigeonhole Principle (formalized below), some residue class must be overcrowded enough to guarantee a collision.
Detecting a Useful Residue Class
After the NTT we have, for each $$$r \in [0, k)$$$, the value $$$\mathit{cnt}[r]$$$: the number of full-array subsets (including $$$\emptyset$$$) with sum congruent to $$$r \pmod k$$$.
Important subtlety. The NTT computes an ordinary (acyclic) convolution, so
box[i]for $$$i \ge k$$$ is nonzero and represents pairs whose sum lands in $$$[k, 2k)$$$ but has remainder $$$i - k$$$ mod $$$k$$$. To get the true $$$\mathit{cnt}[r]$$$ we must fold: $$$\mathit{cnt}[r] = \texttt{box}[r] + \texttt{box}[r + k]$$$ (only one wrap-around term is possible since $$$\max(\sum T_L) + \max(\sum T_R) \lt 2k$$$ for our choice of $$$k$$$... actually for large $$$n$$$ this isn't true in general, but in the code the convolution output naturally has limited wrap-around that the fold handles correctly).
Now, the number of distinct exact sums in residue class $$$r$$$ is at most:
since the exact sums congruent to $$$r \pmod k$$$ form an arithmetic progression $$${r,\, r+k,\, r+2k,\, \ldots}$$$ capped at $$$\sum x_i$$$.
The key Pigeonhole argument: if $$$\mathit{cnt}[r] \gt h$$$, then by the Pigeonhole Principle, at least two of the $$$\mathit{cnt}[r]$$$ subsets in class $$$r$$$ must have the same exact sum — giving us our desired collision. We scan for any such $$$r^*$$$ and focus the search there.
Such an $$$r^*$$$ must exist: if every class had $$$\mathit{cnt}[r] \le h$$$, then $$$\sum_r \mathit{cnt}[r] \le k \cdot h \approx \sum x_i + k$$$. For large $$$n$$$ this is much less than $$$2^n$$$, so the inequality is violated and a crowded class must exist.
Recovering the Answer
We have a target residue $$$r^*$$$ with $$$\mathit{cnt}[r^*] \gt h$$$, guaranteeing a collision in exact sums somewhere in that class. Now we need to actually find the two colliding subsets.
The approach is again meet in the middle, but now restricted to residue class $$$r^*$$$.
Step 1. Enumerate all subsets $$$T_L \subseteq L$$$ with $$$\sum T_L \bmod k = r_L$$$ for each possible $$$r_L$$$. Store them in buckets indexed by $$$r_L$$$: each entry records the exact sum and the bitmask.
Step 2. Enumerate all subsets $$$T_R \subseteq R$$$. For a given $$$T_R$$$ with $$$\sum T_R \bmod k = r_R$$$, the combined sum $$$\sum T_L + \sum T_R$$$ has remainder $$$r^*$$$ iff $$$r_L = (r^* - r_R) \bmod k$$$. So we look up the bucket for residue $$$(r^* - r_R) \bmod k$$$ among the left-half subsets.
Step 3. For each matching pair $$$(T_L, T_R)$$$, compute the exact combined sum $$$s = \sum T_L + \sum T_R$$$. This exact sum lies in $$${r^*,\, r^* + k,\, r^* + 2k,\, \ldots}$$$, so we can index it by $$$q = \lfloor s / k \rfloor$$$, which ranges over at most $$$h$$$ values. We maintain a table mp[q] that stores the first pair seen with that index. The moment we encounter a $$$q$$$ already in the table, we have our collision: two distinct subsets with the same exact sum.
Step 4. Apply Observation 1 to the two colliding subsets to obtain the final disjoint pair.
This enumeration touches at most $$$O(2^{n/2})$$$ subsets per half, consistent with the meet-in-the-middle paradigm.
Correctness Summary
- Existence is guaranteed by Observation 2.
- Compression reduces polynomial degree to $$$k$$$ without losing the ability to detect collisions, because any residue $$$r^*$$$ with $$$\mathit{cnt}[r^*] \gt h$$$ must contain two subsets with the same exact sum (Pigeonhole).
- Recovery finds the collision in $$$O(2^{n/2})$$$ time after the NTT.
- Output transforms the equal-sum pair into a disjoint pair via Observation 1.
Complexity
| Phase | Time |
|---|---|
| Subset enumeration (each half) | $$$O(2^{n/2})$$$ |
| NTT convolution | $$$O(k \log k)$$$ |
| Collision recovery | $$$O(2^{n/2})$$$ |
| Total | $$$O(2^{n/2} + k \log k)$$$ |
With $$$n = 40$$$ and $$$k = 2 \cdot 10^5$$$, both terms are comfortably within time limits.
