LeetCode Online Judge 题目C# 练习 - Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If S = [1,2,3], a solution is:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

 1         public static List<List<int>> Subsets2(List<int> S)
 2         {
 3             S.Sort();
 4             List<List<int>> ret = new List<List<int>>();
 5 
 6             List<int> empty = new List<int>();
 7             ret.Add(empty);
 8 
 9             for (int i = 0; i < S.Count; i++)
10             {
11                 int prev_count = ret.Count;
12                 for (int j = 0; j < prev_count; j++)
13                 {
14                     List<int> temp = new List<int>(ret[j]);
15                     temp.Add(S[i]);
16                     ret.Add(temp);
17                 }
18             }
19 
20             return ret;
21         }

代码分析：

　　DP，第一次做居然想不到，看来复习很重要。 用一个prev_count记录上一次DP的时候做到哪里，不然ret.Count 在里往里 Add 的时候会不停增加的。

 1         public static List<List<int>> Subsets(List<int> S)
 2         {
 3             List<List<int>> ret = new List<List<int>>();
 4             SubsetsRecursive(ret, S, 0);
 5             return ret;
 6         }
 7 
 8         public static void SubsetsRecursive(List<List<int>> ret, List<int> S, int index)
 9         {
10             if (index == S.Count)
11                 ret.Add(new List<int>());
12             else
13             {
14                 SubsetsRecursive(ret, S, index + 1);
15                 int n = ret.Count;
16                 for (int i = 0; i < n; i++)
17                 {
18                     List<int> temp = new List<int>(ret[i]);
19                     temp.Add(S[index]);
20                     ret.Add(temp);
21                 }
22             }
23         }

代码分析：

　　这就是之前想的递归方法，没多大区别。而且还不符合题目 non-descending 的要求。因为递归是从最后一个element开始加的。如果要用这个方法，就要把输入数组 S，descendly sort一次，这里要用到delegate 做 comparsion. 我就懒得做了。

 1         public static List<List<int>> SubsetsCombinatoric(List<int> S)
 2         {
 3             S.Sort();
 4             List<List<int>> ret = new List<List<int>>();
 5 
 6             for (int i = 0; i < (1 << S.Count); i++)
 7             {
 8                 int k = i;
 9                 int index = 0;
10                 List<int> subset = new List<int>();
11                 while (k > 0)
12                 {
13                     if ((k & 1) > 0)
14                     {
15                         subset.Add(S[index]);
16                     }
17                     k >>= 1;
18                     index++;
19                 }
20                 ret.Add(subset);
21             }
22 
23             return ret;
24         }

代码分析：

　　介绍一种比较不一样的方法——Combinatoric。

　　例子： S = { 1, 2, 3}

　　i = 0 : (1 << S.Count - 1) = 0 : 111 (就是S有3个数，i 最大到 111， 4个数， i 最大就到 1111 。。。）

　　然后 k = i； k & 1 == 1 就把相应 S[index] 加到答案里面。然后k >>= 1;

　　k = 0;(0x0)　　{}

　　k = 1;(0x1)　　{1}

　　k = 2;(0x10)　 {2},

　　k = 3;(0x11)　 {1,2};

　　k = 4;(0x100) {3};

　　k = 5;(0x101) {1,3};

　　k = 6;(0x110) {2,3};

　　k = 7;(0x111) {1,2,3};