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:  } 
No comments:
Post a Comment