Sets of squares representing all squares up to $n^2$ Let $S_n=\{1,2,\ldots,n\}$ be natural numbers up to $n$.
Say that a subset $S \subseteq S_n$
square-represents $S_n^2$ if every
square $1^2,2^2,\ldots,n^2$ can be represented by adding or subtracting
at most one copy of squares of elements of $S$.
Example. For $n=7$, the set $S$ of $|S|=5$ numbers
$\{1, 2, 3, 5, 7\}$
square-represents $S_7^2$
because
$4^2 = 5^2 - 3^2$
and $6^2 = 7^2 - 2^2 - 3^2$.
The "at most one copy" condition means that one could represent each
square missing from $S$ by a two-pan balance.
My question is:

Q. What is the minimum size $|S|$ to square-represent $S_n^2$ as $n$ gets large?
  In particular, is this size sublinear, $o(n)$?

In some sense this asks for the frequency of occurrences of Pythagorean triples,
quadruples, and other analogous solutions of equations of the
form $a^2 = b^2 \pm c^2 \pm d^2 \pm \cdots$ with $a,b,c,d,\ldots$ distinct.
This may be well-known to the experts, in which case I apologize for asking a naive question.
 A: We can have the size of $S$ as small as $c \ln(n)$ for some constant $c$, and we can do this in such a way that every element of $\{1, 2, \ldots, n^2 \}$ can be represented by adding or subtracting at most copy of a square of something in $S$. I will construct a sequence of sets $T_{k}$ so that $T_{k}$ has size $k$, and every number $\leq (3/2)^{k}$ can be represented in the desired way.
Define a sequence by $a_{1} = 1$, $a_{2} = 2$, $a_{3} = 3$, $a_{4} = 4$, $a_{5} = 5$.
Every integer $1 \leq m \leq 42$ can be represented in the desired way using elements of $\{ 1, 2, 3, 4, 5 \}$. Let $b_{5} = 42$. For $k \geq 5$, let $a_{k+1} = \lfloor \sqrt{b_{k}} \rfloor$ and $b_{k+1} = b_{k} + a_{k+1}^{2}$. Define $T_{k+1} = \{ a_{1}, a_{2}, \ldots, a_{k}, a_{k+1} \}$. Then, by construction, every number between $1$ and $b_{k}$ can be represented using the elements of $T_{k}$ and every number between $b_{k}+1$ an $b_{k+1}$ can be represented in the form $a_{k+1}^{2} + r$, where $1 \leq r \leq b_{k}$.
In particular, every square between $1$ and $b_{k+1}$ can be represented in the desired way using elements of $T_{k}$. Moreover, it is easy to see that $a_{k+1} > a_{k}$ and $b_{k+1} \geq (3/2) b_{k}$ (and in fact, $b_{k+1} \approx 2b_{k}$). For an $S$ constructed in this way, we have $|S| = k$ and $n = \lfloor \sqrt{b_{k}} \rfloor \geq (\sqrt{3/2})^{k}$. 
A trivial lower bound on $|S|$ is $\ln(n)/\ln(3)$, just because there are $3^{|S|}$ possible sums $\sum_{s \in S} \epsilon_{s} s$, where $\epsilon_{s} \in \{ -1, 0, 1 \}$.
A: Here is a little example following Jeremy Rouse's construction. Let $A$ be the $a_i$ terms
and $B$ the $b_i$ terms.
$$A=\{1,2,3,4,5,6,8,11,16\}$$
$$B=\{0,0,0,0,42,78,142,263,519\}$$
For example 
$$a_9 = \lfloor \sqrt{b_8} \rfloor = \lfloor \sqrt{263} \rfloor = 16 \;,$$
and
$$b_9=b_8+a^2_9 = 263+16^2 = 519 \;.$$
The missing squares can be achieved as follows:
$$7^2 = 2^2 + 3^2 + 6^2$$
$$9^2 = 1^2 + 4^2 + 8^2$$
$$10^2 = 6^2 + 8^2$$
$$12^2 = 3^2 - 11^2 + 16^2$$
$$13^2 = -4^2+ 8^2+ 11^2$$
$$14^2 = 2^2 -8^2 + 16^2$$
$$15^2 = 1^2 + 2^2 - 6^2 + 16^2$$
