This problem is solved by visual inspection of the NPC. It can be divided into "two steps".

1. Find all "additional subsets". Take each element as a possible sum and use the subset sum algorithm to solve it one by one.

2. Find the maximum union of mutually exclusive additive subsets: refer to the set packing algorithm and use linear programming to solve it.

The following uses Mathematica to describe the algorithm in detail.

Find addition subset

To enumerate all the numbers that constitute the addition formula in the set (allowing negative numbers and repeated numbers), first use the subset sum algorithm (recursion with caching) to enumerate the subsets whose sum is a given number .

subsetSum[lst_List, s_] := Block[{q},
  q[k_?NonPositive, x_] := {};
  q[k_?Positive, x_] := q[k, x] =
    Union[q[k - 1, x],
     If[lst[[k]] == x, {{x}}, {}],
     (Append[lst[[k]]] /* Sort) /@ q[k - 1, x - lst[[k]]]];
  q[Length[lst], s]]

code makes a recursive call to q and caches the results. For specific recursive derivation, please refer to this question. Note that the calculated addition subsets are sorted internally, and finally a union operation is performed to remove duplicates. Use case:

subsetSum[{1, 2, 3, 4, 5}, 8]
> {{3, 5}, {1, 2, 5}, {1, 3, 4}}

The given number may be any element in the set in this problem, so use subsetSum to iterate through each element in the set and try to form an addition with it and the remaining elements. Finally, the duplicate combinations are removed, which is the total possible addition subset.

summationList[lst_List] := Union @@ Array[
   i \[Function] Map[Append[lst[[i]]] /* Sort,
     Select[subsetSum[Delete[lst, i], lst[[i]]], Length[#] > 1 &]],
   Length[lst]]

The above code also performs an internal sorting operation on the set, because the order may be disrupted when adding sum and sum to the set. And the case where the number of addends is less than 2 is deleted. Use case:

summationList[{1, 2, 3, 4, 5}]
> {{1, 2, 3}, {1, 3, 4}, {1, 4, 5}, {2, 3, 5}}

Find mutually exclusive maximum union

After obtaining the addition subset, use weighted set packing to find the mutually exclusive maximum union among them. To describe it in linear programming language is

$$array{text{maximize} & sum{|s_i| The sets are mutually exclusive} \ & x_i in {0, 1} & text{$x_i=1$, then select the set $i$, otherwise abandon the set $i$}}$$

Mathematica provides built-in LinearProgramming functions:

pickSumList[lst_List] := Module[{sumlst},
  sumlst = summationList[lst];
  Pick[sumlst,
   LinearProgramming[
    -Length /@ sumlst,
    Outer[MemberQ[#2, #1] & /* Boole, lst, sumlst, 1],
    ConstantArray[{1, -1}, Length[lst]],
    ConstantArray[{0, 1}, Length[sumlst]],
    Integers],
   1]]

Test

Example of topic:

Randomly generate a set of 16 elements.

Find results with pickSumList and highlight elements that are sums:

Remaining elements: