Solution: If $a_i + a_j$ can be the same value for different pairs of $i$ and $j$, then for any $n$, we can simply take $a_n = n$, making the problem trivial. Therefore, we will handle the problem under the assumption that $a_i + a_j$ are all distinct for different pairs of $i$ and $j$. When $n = 3$, let $a_1 = 1, a_2 = 2, a_3 = 3$, then the set $\{x | x = a_i + a_j\} = \{3, 4, 5\}$ satisfies the condition. When $n = 4$, let $a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 5$, then the set $\{x | x = a_i + a_j\} = \{3, 4, 5, 6, 7, 8\}$ also satisfies the condition. For $n \geq 5$, assume without loss of generality that $a_1 < a_2 < \cdots < a_n$. The set of all $a_i + a_j$ forms an arithmetic sequence with a common difference of $d$. Then, $a_1 + a_2$ is the smallest term in the sequence, and $a_1 + a_3$ is the second smallest, thus $a_3 = a_2 + d$. Similarly, $a_{n-1} + a_n$ is the largest term in the sequence, and $a_{n-2} + a_n$ is the second largest, thus $a_{n-1} = a_{n-2} + d$. At this point, $a_2 + a_{n-1} = a_3 + a_{n-2}$, which is a contradiction. Therefore, $n$ can only be 3 or 4.