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:  }

All possible subsets of set with duplicates removed

Given a set of character {a, b, c, d} find all subsets. The final list should not have any duplicate entry.

   1:  /// <summary>

   2:  /// Given set {a, b, c, d} below are all subsets 

   3:  ///     d

   4:  ///     dc     c     

   5:  ///     dca    cb     b   a

   6:  ///     dcba   cba    ba

   7:  ///     dca    ca

   8:  ///     db

   9:  ///     dba

  10:  ///     da

  11:  ///  This algortithm picks an item from input set and prepends it with items present in output set as well as adds the item

  12:  ///  This guarantees unordered combinations. i.e. it treats "ab" and "ba" same ways.

  13:  /// </summary>

  14:  /// <param name="data"></param>

  15:  /// <returns></returns>

  16:  static List<string> GetAllSubsets(char[] data)

  17:  {

  18:      List<string> result = new List<string>();

  19:      for (int i = 0; i < data.Length; i++)

  20:      {

  21:          for (int j = result.Count - 1; j >= 0; j--)

  22:          {

  23:              StringBuilder sb = new StringBuilder(result[j]);

  24:              sb.Insert(0, data[i]);

  25:              result.Add(sb.ToString());

  26:          }

  27:          result.Add(new string(new char[] { data[i] }));

  28:      }

  29:   

  30:      return result;

  31:  }