[Tutorial] CSES — Same Sum Subsets

Revision en2, by abner_vidal, 2026-04-07 03:03:58

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:

$$$ \sum_{x \in A'} x = \sum_{x \in A} x - \sum_{x \in A \cap B} x = \sum_{x \in B} x - \sum_{x \in A \cap B} x = \sum_{x \in B'} x. $$$

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

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:

$$$ P_S(x) = \sum_{T \subseteq S} x^{\,\sum_{a \in T} a}. $$$

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:

$$$ P(x) = P_L(x) \cdot P_R(x). $$$

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:

$$$ \tilde{P}_S(x) = P_S(x) \bmod (x^k - 1) = \sum_{r=0}^{k-1} \left( \sum_{\substack{T \subseteq S \\ \sum T \equiv r \pmod{k}}} 1 \right) x^r. $$$

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:

$$$ \sum_{r=0}^{k-1} \mathit{cnt}[r] = 2^n. $$$

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

  1. Existence is guaranteed by Observation 2.
  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).
  3. Recovery finds the collision in $$$O(2^{n/2})$$$ time after the NTT.
  4. 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.

Implementation

Implementation
Tags ntt, fft, pigeonhole principle, meet in the middle, cses, solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English abner_vidal 2026-04-07 03:38:33 2268
en7 English abner_vidal 2026-04-07 03:23:25 29
en6 English abner_vidal 2026-04-07 03:18:19 57 Tiny change: '# Equal-Sum Disjoint Subsets: An FFT-Based Approach\n\n## Introdu' -> '## Introdu'
en5 English abner_vidal 2026-04-07 03:17:57 13886 (published)
en4 English abner_vidal 2026-04-07 03:10:17 10
en3 English abner_vidal 2026-04-07 03:06:17 30
en2 English abner_vidal 2026-04-07 03:03:58 18243
en1 English abner_vidal 2026-04-07 02:55:01 4285 Initial revision (saved to drafts)