Find the optimal set of weights to add to a certain set of weights In this challenge, you will recieve a comma-separated list of weights as input, such as

1,3,4,7,8,11


And you must output the smallest amount of weights that can add to that set. For example, the output for this set would be

1,3,7


Because you could represent all of those weights with just those three:

1     = 1
3     = 3
1+3   = 4
7     = 7
1+7   = 8
1+3+7 = 11


There may be more than one solution. For example, your solution for the input 1,2 could be 1,1 or 1,2. As long as it finds the minimum amount of weights that can represent the input set, it is a valid solution.

Weights may not be used more than once. If you need to use one twice, you must output it twice. For example, 2,3 is not a valid solution for 2,3,5,7 because you can't use the 2 twice for 2+2+3=7.

Input is guaranteed not to have duplicated numbers.

This is code-golf so shortest code by character count wins.

Network access is forbidden (so none of your "clever" wget solutions @JohannesKuhn cough cough) ;)

Simpleest cases:

1,5,6,9,10,14,15               =&gt; 1,5,9
7,14,15,21,22,29               =&gt; 7,14,15
4,5,6,7,9,10,11,12,13,15,16,18 =&gt; 4,5,6,7
2,3,5,7                        =&gt; 2,2,3 or 2,3,7


And some trickier ones:

10,16,19,23,26,27,30,37,41,43,44,46,50,53,57,60,61,64,68,71,77,80,84,87
  =&gt; 3,7,16,27,34
20,30,36,50,56,63,66,73,79,86
  =&gt; 7,13,23,43
27,35,44,46,51,53,55,60,63,64,68,69,72,77,79,81,86,88,90,95,97,105,106,114,123,132
  =&gt; 9,18,26,37,42
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.