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