Find the optimal set of weights to add to a certain set of weights
Mathematica 80 75

Update: See at bottom an update on Doorknob's challenging last test, added on Nov.5



This passes all but the last test. However, it does not attempt to use a digit more than once.  And it only searches from solutions that are subsets of the larger data set. 

The function generates all of the subsets of the input data set and then tests which subsets can be used to construct the complete set. After the viable subsets are found, it chooses the smallest sets.

s=Subsets
f@i_:=GatherBy[Select[s@i,Complement[i, Total /@ s@#]=={}&amp;],Length]〚1〛


Tests

f[{1, 3, 4, 7, 8, 11}]



  {{1, 3, 7}} 




f[{1, 5, 6, 9, 10, 14, 15}]



  {{1, 5, 9}}  




f[{7, 14, 15, 21, 22, 29}]



  {{7, 14, 15}}  




f[{4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 18}]



  {{4, 5, 6, 7}} 




f[{2, 3, 5, 7}]



  {{2, 3, 5}, {2, 3, 7}}




Update

Below I'll provide an initial analysis that may help get started toward a solution.

The data:

data = {10, 16, 19, 23, 26, 27, 30, 37, 41, 43, 44, 46, 50, 53, 57, 60, 61, 64, 68, 71, 77, 80, 84, 87};


Differently from the earlier approach, we want to consider, in the solution set, numbers that do NOT appear in the data set.

The approach makes use of absolute differences between pairs of numbers in the data set.

g[d_] := DeleteCases[Reverse@SortBy[Tally[Union[Sort /@ Tuples[d, {2}]] /. {a_, b_} :&gt; Abs[a - b]], Last], {0, _}] 


Let's look at the number of times each difference appears; we'll only grab the first 8 cases, starting from the most common difference].

g[data][[1;;8]]



  {{7, 14}, {27, 13}, {34, 12}, {3, 11}, {20, 10}, {16, 10}, {4, 
    10}, {11, 9}}


14 pairs differed by 7; 13 pairs differed by 27, and so on.

Now let's test subsets starting with {difference1},{difference1, difference2}, and so on, until we can hopefully account for all the original elements in the data set.

h reveals those numbers from the original set that cannot be constructed by composing sums from the subset.

h[t_] := Complement[data, Total /@ Subsets@t]


By the fifth try, there are still 10 elements that cannot be formed from {7, 27, 34, 3, 20}:

h[{7, 27, 34, 3, 20}]



  {16, 19, 26, 43, 46, 53, 60, 77, 80, 87}


But on the next try, all numbers of the data set are accounted for:

h[{7, 27, 34, 3, 20, 16}]



  {}


This is still not as economical as {3,7,16,27,34}, but it's close.



There are still some additional things to take into account.


If 1 is in the data set, it will be required in the solution set.
There may well be some "loners" in the original set that cannot be composed from the most common differences. These would need to be included apart from the difference tests.


These are more issues than I can handle at the moment. But I hope it sheds some light on this very interesting challenge.