Proof in the case $n$ is odd
By Sylow's 1st theorem there is a subgroup $H \vartriangleleft G$ of order (at least) 2 × 2 × 2 = 8. This could be one of five possibilities:
- $\mathbb{Z}_8, \mathbb{Z}_4 \times \mathbb{Z}_2, \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2$ and additionally
- $ D_8 \simeq \mathbb{Z}_4 \rtimes \mathbb{Z}_2, Q = (\mathbb{Z}_2 \times \mathbb{Z}_2) \rtimes \mathbb{Z}_2 $. The dihedral group and quaternion group.
In the Abelian case, it is clear there are eight conjugacy classes - 1 for each element. Since $H$ is normal, these extend to conjugacy classes of $G$.
In the Dihedral case, the rotations form a normal subgroup: $\mathbb{Z}_4 \vartriangleleft D_8 $. This leads to 4 conjugacy classes + 2 for the reflections. These are the symmetries of a square (See List all subgroups of the symmetry group of $n$-gon).
The quaternion group $\langle i,j,k | i^2 = j^2 = k^2 = ijk=-1\rangle$ has 6 conjugacy classes.
Representation theory makes it as simple as the sumset identity ($7$ is missing):
$$ \{ 0^2,1^2,2^2\} + \{ 0^2,1^2,2^2\} + \{ 0^2,1^2,2^2\} \subset \{0, 1,2,3,4,5,6,7\}$$
Sylow theorem guaranteed us a large enough normal subgroup; this is clearly the way to go.
The problem is reduced to the detailed study of the partitions and permutations involves the number 8 and related coincidences.