tryingout: All possible ways of getting to a target sum

Suppose we are given infinite supply of {5,20,25} cents coins. What are the possible ways of get 1$?

We can solve above problem by backtracking algorithm as given below

   1:  private static void GetAllArrangements(int[] set, int index, int target, Dictionary<int, int> partialResult, List<List<int>> result)

   2:  {

   3:      for (int i = index; i < set.Length; i++)

   4:      {

   5:          int item = set[i];

   6:          int newTarget = target - item;

   7:          if (newTarget == 0)

   8:          {

   9:              if (!partialResult.ContainsKey(item))

  10:              {

  11:                  partialResult.Add(item, 1);

  12:              }

  13:              else

  14:              {

  15:                  partialResult[item]++;

  16:              }

17:

  18:              List<int> newArrangement = new List<int>();

  19:              foreach (var item2 in set)

  20:              {

  21:                  int count = 0;

  22:                  partialResult.TryGetValue(item2, out count);

  23:                  newArrangement.Add(count);

  24:              }

25:

  26:              result.Add(newArrangement);

  27:              partialResult[item]--;

  28:          }

  29:          else if (newTarget >= set[0])

  30:          {

  31:              if (!partialResult.ContainsKey(item))

  32:              {

  33:                  partialResult.Add(item, 1);

  34:              }

  35:              else

  36:              {

  37:                  partialResult[item]++;

  38:              }

39:

  40:              GetAllArrangements(set, i, newTarget, partialResult, result);

  41:              partialResult[item]--;

  42:          }

  43:      }

  44:  }

tryingout