An easy way, using PowersRepresentations[]:
$PowersRepresentations[n,k,p] $ gives the distinct representations of the integer n as a sum of k non-negative p^th integer powers.
s1 = Join@@ (Select[PowersRepresentations[748,#,2], Intersection[#, Range@16] == # &] & /@ Range@8)
Gives all possible ways to total 748.
For filtering the ones that are complementary:
s = Tally[s1, Union[#1, #2] == Range@16 &][[All, 1]];
Length@s
(*
57
*)