Combination Algorithm

I haven't checked your code, so I can't say what is wrong with it but for an input of 2386 the following code gives these answers (runtime is 127mS on my computer

618,618,618,300,232

618,618,350,350,250,200

618,618,350,300,300,200

618,618,350,300,250,250

618,618,350,200,200,200,200

618,618,308,250,232,232,128

618,618,300,300,300,250

618,618,300,250,200,200,200

618,618,250,250,250,200,200

618,350,350,308,232,200,200,128

618,350,350,300,128,128,128,128,128,128

618,350,308,300,250,232,200,128

618,350,308,250,250,250,232,128

618,350,250,200,200,128,128,128,128,128,128

618,308,308,232,232,232,200,128,128

618,308,308,128,128,128,128,128,128,128,128,128

618,308,300,300,300,232,200,128

618,308,300,300,250,250,232,128

618,308,300,232,232,232,232,232

618,308,300,232,200,200,200,200,128

618,308,250,250,232,200,200,200,128

618,300,300,200,200,128,128,128,128,128,128

618,300,250,250,200,128,128,128,128,128,128

618,250,250,250,250,128,128,128,128,128,128

618,232,232,232,232,200,128,128,128,128,128

618,232,128,128,128,128,128,128,128,128,128,128,128,128

618,200,200,200,200,200,128,128,128,128,128,128

350,350,350,350,350,308,200,128

350,350,350,350,308,300,250,128

350,350,350,308,308,232,232,128,128

350,350,350,308,300,300,300,128

350,350,350,308,300,200,200,200,128

350,350,350,308,250,250,200,200,128

350,350,350,232,232,232,128,128,128,128,128

350,350,308,308,308,250,128,128,128,128

350,350,308,300,300,250,200,200,128

350,350,308,300,250,250,250,200,128

350,350,308,250,250,250,250,250,128

350,350,308,250,232,232,232,232,200

350,350,308,250,232,128,128,128,128,128,128,128

350,350,308,250,200,200,200,200,200,128

350,308,308,308,300,300,128,128,128,128

350,308,308,308,200,200,200,128,128,128,128

350,308,308,300,232,232,200,200,128,128

350,308,308,250,250,232,232,200,128,128

350,308,300,300,300,300,200,200,128

350,308,300,300,300,250,250,200,128

350,308,300,300,250,250,250,250,128

350,308,300,300,232,232,232,232,200

350,308,300,300,232,128,128,128,128,128,128,128

350,308,300,300,200,200,200,200,200,128

350,308,300,250,250,232,232,232,232

350,308,300,250,250,200,200,200,200,128

350,308,250,250,250,250,200,200,200,128

350,308,232,232,232,232,200,200,200,200

350,308,232,200,200,200,128,128,128,128,128,128,128

350,308,200,200,200,200,200,200,200,200,128

350,300,232,232,232,200,200,128,128,128,128,128

350,300,200,128,128,128,128,128,128,128,128,128,128,128,128

350,250,250,232,232,232,200,128,128,128,128,128

350,250,250,128,128,128,128,128,128,128,128,128,128,128,128

308,308,308,300,250,200,200,128,128,128,128

308,308,308,250,250,250,200,128,128,128,128

308,308,300,300,250,232,232,200,128,128

308,308,300,250,250,250,232,232,128,128

308,308,250,232,232,232,232,232,232,128

308,308,250,232,232,200,200,200,200,128,128

308,300,300,300,300,300,250,200,128

308,300,300,300,300,250,250,250,128

308,300,300,300,250,232,232,232,232

308,300,300,300,250,200,200,200,200,128

308,300,300,250,250,250,200,200,200,128

308,300,250,250,250,250,250,200,200,128

308,300,250,232,232,232,232,200,200,200

308,300,250,232,200,200,128,128,128,128,128,128,128

308,300,250,200,200,200,200,200,200,200,128

308,250,250,250,250,250,250,250,200,128

308,250,250,250,232,232,232,232,200,200

308,250,250,250,232,200,128,128,128,128,128,128,128

308,250,250,250,200,200,200,200,200,200,128

300,300,250,232,232,232,200,128,128,128,128,128

300,300,250,128,128,128,128,128,128,128,128,128,128,128,128

300,250,250,250,232,232,232,128,128,128,128,128

250,232,232,232,232,232,232,232,128,128,128,128

250,232,232,232,200,200,200,200,128,128,128,128,128

250,200,200,200,128,128,128,128,128,128,128,128,128,128,128,128

void Main()
{
  int target = 2386;
  var available = new List<int>{618,350,308,300,250,232,200,128};
        
  foreach (var result in findCombinations(target, 0,new List<int>(), available))
  {
    stringList(result).Dump();
  }
}

IEnumerable<IEnumerable<int>> findCombinations(int target, int soFar, IList<int> used, IEnumerable<int> available)
{
  if (available.Count () == 0) yield break;
  var first = available.First ();
  var usedNow = new List<int>(used);
  
  // Adding the first available number gets the result we want
  if (soFar + first == target) {
    // add the first number and return the list
    usedNow.Add(first);
    yield return usedNow;
  } else 
  // Adding the first number leaves us short, so append the number to the usedNow list, increment soFar and try
  // again with the same set of available numbers
  if (soFar + first < target) {
    usedNow.Add(first);
    foreach (var element in findCombinations(target, soFar+first, usedNow, available))
    {
      yield return element;
    }
  }
  // Otherwise adding the first number takes us over the total, just skip that combination
  
  // Whatever happened, try again with the same inputs but skip the first available number
  foreach (var element in findCombinations(target, soFar, used, available.Skip(1)))
  {
    yield return element;
  }
}

string stringList(IEnumerable<int> nums)
{
if (!nums.Any ( )) return string.Empty;
 return nums.Select (r => r.ToString()).Aggregate ((t,r) =>t+","+r );
 }
        

Is that what you want?

(The call to Dump() is a Linqpad.net provided method - you could replace it with Console.WriteLine())

---

Paul Linton