Math to the rescue!
You can check that every even number larger than 8 is a linear combination of elements from this set - ask on Math Overflow for a proof ;).
So let's rephrase the question in math:
- We have an overcomplete dictionary of basis vectors (because 16, for example, is a multiple of 8),
- in which we can represent every even number larger than 8 as a linear combination of these basis vectors, and
- we are trying to minimize the zero "norm" of this input vector.
The good news: This is a very interesting problem, with many application domains, so it is pretty well researched.
The bad news: this is still a hard (NP-hard) problem.
But, hey, at least now you know.
edit:
And just so I don't get accused of handwaving philosophical answer, here's a modified (completely non-optimized) version of Solver.recursiveSolve
that exhaustively searches for a combination of segments that match the goal; and a zero norm comparer class with which you can sort your results:
private void RecursiveSolve(int goal, int currentSum,
List<int> included, List<int> segments, int startIndex)
{
for (int index = 0; index < segments.Count; index++)
{
int nextValue = segments[index];
if (currentSum + nextValue == goal)
{
List<int> newResult = new List<int>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum + nextValue < goal)
{
List<int> nextIncluded = new List<int>(included);
nextIncluded.Add(nextValue);
RecursiveSolve(goal, currentSum + nextValue,
nextIncluded, segments, startIndex++);
}
}
}
class ZeroNormAndSDComparer : IComparer<List<int>>
{
private int l0_norm(List<int> v)
{
int norm = 0;
HashSet<int> seen = new HashSet<int>();
for (int i = 0; i < v.Count; ++i)
{
if (!seen.Contains(v[i]))
{
norm++;
seen.Add(v[i]);
}
}
return norm;
}
private static double StandardDeviation(List<int> v)
{
double M = 0.0;
double S = 0.0;
int k = 1;
foreach (double value in v)
{
double tmpM = M;
M += (value - tmpM) / k;
S += (value - tmpM) * (value - M);
k++;
}
return Math.Sqrt(S / (k - 1));
}
public int Compare(List<int> x, List<int> y)
{
int normComparison = l0_norm(x).CompareTo(l0_norm(y));
if (normComparison == 0)
{
return StandardDeviation(x).CompareTo(StandardDeviation(y));
}
return normComparison;
}
}
And your modified Main (now sorting is done after results have been reduced to distinct, 4-segment results):
List<int> nums = new List<int>() { 8, 10, 12, 14, 16, 18, 20, 22, 24 };
int width = 80;
Console.WriteLine("Total width: " + width);
Solver solver = new Solver();
List<List<int>> res = solver.Solve(width, nums.ToArray());
Console.WriteLine("total :" + res.Count);
var res1 = res.Distinct(new SequenceComparer<List<int>, int>()).ToList();
Console.WriteLine("total res1:" + res1.Count);
var res2 = res1.Where(l => l.Count == 4).ToList();
Console.WriteLine("total res2:" + res2.Count); //reduce to 4 integer solutions
res2.Sort(new ZeroNormAndSDComparer());