Working on such problems, I am convinced that there is no greedy algorithm that can guarantee an optimal result. However, there is no need to look at each combination of two numbers at each step.
After looking at a few examples, it is obvious that the first number you use should always be the largest. For lists of 3 or 4 items, subtracting the second largest number is always the best choice. However, for lists of 5 items or more, there seems to be no general rule.
10,4,3,2,1 -> 6,3,2,1 -> 3,2,1 -> 1,1 -> 1 (largest minus 2nd-largest: 10-6=4) 10,4,3,2,1 -> 9,4,3,2 -> 5,3,2 -> 2,2 -> 2 (largest minus smallest: 10-1=9)
9,8,7,6,5 -> 1,7,6,5 -> 1,1,5 -> 1,4 -> 3 (largest minus 2nd-largest: 9-8=1) 9,8,7,6,5 -> 4,8,7,6 -> 4,1,6 -> 2,1 -> 1 (largest minus smallest: 9-5=4)
I tested an algorithm that tries both the smallest and second largest number for each step (as a result of 2 n recursion), but found an example where this does not work: 99,78,68,56,52,4,3 ,
The best solution found using only the smallest or second largest is 6:
99 78 68 56 52 4 3 96 78 68 56 52 4 92 78 68 56 52 40 78 68 56 40 10 56 10 16 6
The best solution found by force formatting all parameters: 1:
99 78 68 56 52 4 3 31 78 56 52 4 3 31 26 56 4 3 26 25 4 3 1 4 3 1 1
If you use the largest number as the only optimization, this will result in the following algorithm:
- Find the highest number
- Iterate over all the remaining numbers, subtract them from the largest number and recurse
This would have a lower time complexity than trying each combination of two numbers or sorting after each step.