Showing posts with label all subsets without duplicates. Show all posts
Showing posts with label all subsets without duplicates. Show all posts

Monday, 19 September 2011

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