How to find all possible values of 100 dollar bill

Question

banknotes provided = 10 Dollar, 50 Dollar, 100 Dollar

Expected Result for 100 dollar bill with above bank notes. I want to show the denomination exactly like below

5 x 10 + 1x 50
2 x 50 
1 x 100 
10 x 10  

As you can see all the banknotes denomination total to 100 above

Answer 1

Let's split the problem in two:

1. Solve the exchange problem of total given notes (in descending order), starting from nominal at index.
2. Provide the solution in required format

Code:

private static IEnumerable<int[]> Solutions(int total, int[] notes, int index) {
  int value = notes[index];

  if (index == notes.Length - 1) {
    if (total % value == 0)
      yield return new int[] { total / value };
  }
  else 
    for (int i = total / value; i >= 0; --i) 
      foreach (int[] rest in Solutions(total - value * i, notes, index + 1))
        yield return rest.Prepend(i).ToArray();
}

private static IEnumerable<string> Solve(int total, int[] notes) {
  var items = notes.OrderByDescending(item => item).ToArray();

  foreach (int[] solution in Solutions(total, items, 0)) 
    yield return string.Join(" + ", solution
      .Zip(items, (count, note) => (count, note))
      .Where(pair => pair.count > 0)
      .Select(pair => $"{pair.count} x {pair.note}"));
}

Demo:

int total = 170;
int[] notes = new int[] {10, 50, 100};

Console.Write(string.Join(Environment.NewLine, Solve(total, notes)));

Output:

1 x 100 + 1 x 50 + 2 x 10
1 x 100 + 7 x 10
3 x 50 + 2 x 10
2 x 50 + 7 x 10
1 x 50 + 12 x 10
17 x 10

Fiddle