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$$$.
Proof. Define $$$A' = A \setminus B$$$ and $$$B' = B \setminus A$$$. Since $$$A \neq B$$$, it is impossible that both $$$A' = \emptyset$$$ and $$$B' = \emptyset$$$, so at least one is nonempty. Furthermore:
We claim neither $$$A'$$$ nor $$$B'$$$ can be empty. If $$$A' = \emptyset$$$, then the first equality gives $$$\sum_{x \in A} x = \sum_{x \in A \cap B} x$$$, and combined with the last equality, $$$\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.
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.
Finding the Collision via Meet in the Middle
Existence is guaranteed; we now need to find the two subsets efficiently.
We split the array into two halves $$$L$$$ and $$$R$$$, each of size at most $$$\lceil n/2 \rceil \le 20$$$.
For a set $$$S$$$, define its subset-sum generating polynomial:
The coefficient of $$$x^k$$$ in $$$P_S(x)$$$ equals the number of subsets of $$$S$$$ whose elements sum to $$$k$$$. We compute $$$P_L(x)$$$ and $$$P_R(x)$$$, then form:
The coefficient of $$$x^k$$$ in $$$P(x)$$$ counts the number of pairs $$$(T_L, T_R)$$$ with $$$T_L \subseteq L$$$, $$$T_R \subseteq R$$$, and $$$\sum_{a \in T_L \cup T_R} a = k$$$; equivalently, it counts subsets of the full array summing to $$$k$$$. A coefficient of $$$2$$$ or more at any $$$x^k$$$ certifies a 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.
Instead, we work modulo $$$x^k - 1$$$ for a suitably chosen integer $$$k$$$ (equivalently, we track sums modulo $$$k$$$). Define the compressed polynomial:
The coefficient of $$$x^r$$$ in $$$\tilde{P}_L(x) \cdot \tilde{P}_R(x)$$$ then counts pairs $$$(T_L, T_R)$$$ whose combined sum is congruent to $$$r \pmod k$$$. All arithmetic is now on polynomials of degree at most $$$k-1$$$, and NTT runs in $$$O(k \log k)$$$.
Choosing $$$k$$$. We set $$$k \approx 2 \cdot 10^5$$$. The total number of subsets is $$$2^n \ge 2^3 = 8$$$, and by Observation 2 the number of distinct exact sums is at most $$$2^n - 2$$$. So the average number of subsets per residue class modulo $$$k$$$ is $$$2^n / k$$$. For $$$n = 40$$$, this is roughly $$$2^{40} / (2 \cdot 10^5) \approx 5 \cdot 10^6$$$, meaning many residue classes will have a very large number of subsets — far more than necessary to guarantee collisions when we enumerate.
Detecting a Useful Residue Class
Let $$$\mathit{cnt}[r]$$$ denote the coefficient of $$$x^r$$$ in $$$\tilde{P}(x) = \tilde{P}_L(x) \cdot \tilde{P}_R(x)$$$, i.e., the number of full-array subsets with sum $$$\equiv r \pmod{k}$$$.
The total number of subsets (including the empty set) is $$$2^n$$$, so:
The number of possible exact sums congruent to $$$r \pmod k$$$ is at most $$$\lfloor (\sum x_i) / k \rfloor + 1 =: h$$$. Thus, for a collision (two subsets with the same exact sum) to be guaranteed among all subsets with sum $$$\equiv r \pmod k$$$, we need $$$\mathit{cnt}[r] \gt h$$$ by the Pigeonhole Principle.
We scan for any residue $$$r$$$ with $$$\mathit{cnt}[r] \gt h$$$ and focus our search there.
Recovering the Answer
We now have a target residue $$$r^*$$$ such that more subsets map to $$$r^*$$$ than there are distinct exact sums congruent to $$$r^* \pmod k$$$.
Step 1. Enumerate all subsets $$$T_L \subseteq L$$$ with $$$\sum T_L \equiv r^* \pmod k$$$. For each, record its exact sum and bitmask.
Step 2. Enumerate all subsets $$$T_R \subseteq R$$$. For each mask $$$T_R$$$ with $$$\sum T_R \equiv s \pmod k$$$, look up the bucket for residue $$$(r^* - s) \bmod k$$$ among the left-half subsets. For each pair $$$(T_L, T_R)$$$ in that bucket, their combined exact sum is $$$\sum T_L + \sum T_R$$$. Group these pairs by their exact combined sum (indexed by $$$\lfloor (\sum T_L + \sum T_R) / k \rfloor$$$, which fits in a flat array of size $$$h$$$).
Step 3. The first time a bucket in Step 2 is hit for the second time, we have found two distinct subsets $$$A = T_L^{(1)} \cup T_R^{(1)}$$$ and $$$B = T_L^{(2)} \cup T_R^{(2)}$$$ with the same exact sum. Apply Observation 1 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.
