Because 33<2*42, we know that for all x>32 in S3,4 there is a smaller element greater than x/2 also in S. (If x=3a4b, with b>0, use 3a+14b-1. Otherwise, we know that a≥3, so use 3a-34b+2.)
Therefore, by taking any n and subtracting from it, recursively, the largest element of S that is less than or equal to n, one can always reduce n to a number smaller than 9. In fact, by continuing to subtract the largest element no greater than the residue that is still unused, we can reduce n down to either 0 or 1. Thus, either n is a subset sum or n-1 is.
Now, take these subsets and multiply all their elements by 4. This makes them still in S3,4 and still distinct, and shows that any number of the form 4n can be reduced in this way to either 0 or 4. Because neither 1 nor 3 divides by 4, these are unused, so we can subtract a further 1+3 where needed, to prove that any multiple of 4 is a subset sum of S3,4.
If n is not a multiple of 4, we can begin by subtracting from it 9, 9+81 or 27, as may be appropriate, to make it divide by 4, then use the method for numbers divisible by 4 to complete the rest. This proves that all n≥9+81 are subset sums.
Q.E.D.
The actual list of integers that are not subset sums of S3,4 is {2,6,11,18,54}.
Regarding the bonus question, to prove that the same is true for all Sp,q with co-prime p, q>1, I must thank Li Li, again, for forwarding the relevant papers to me.
Turns out that this problem was initially posed as a conjecture by the great Hungarian mathematician Paul Erdős, and first solved by the British mathematician Bryan John Birch -- ingeniously -- in
B. J. Birch, Note on a problem of Erdős, Math. Proc. Cambridge Phil. Soc. 55, 370-373, 1959.
Birch's proof is short, elegant and elementary: exactly the kind of proof we like to see here, at Using your Head is Permitted. I won't repeat it on this page, but readers are encouraged to check out the link. I'll mention here only one stroke of brilliance of the proof: Birch initially relaxes the question to allow also pxqy values where x and/or y are negative.
Following up on Birch's result, but using much heavier mathematical machinery, Birch's own doctoral advisor, John William Scott Cassels, proved a similar result regarding general sets, not just ones generateable as powers, showing that restricting the rate at which members of the set become increasingly rare as the numbers involved increase, while demanding that the numbers in the set are diverse enough (e.g., not all divisible by some k), is enough to ensure that all integers except for finitely many can be represented as subset sums. The number of "missing" integers can be quite large, however.
Cassels's proof can be found in
These results have been further generalised in many papers, including recent ones, and the topic seems to be under continuous study. One particularly interesting follow-up was by Erdős himself. It was published only a few months before Erdős's death.
The innovation here is that the elements taken from the set to create a sum must also not have pairs that divide each other. Erdős and Lewin show (in an elementary fashion) that {pxqy} covers all integers in this way (with or without a finite number of exceptions) if and only if {p, q}={2,3}. Similar results, with similar methods, are given regarding {pxqyrz}, for various {p, q, r}.