LeetCode Online Judge 题目C# 练习 - Combination

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4]

 1         public static List<List<int>> Combination(int n, int k)
 2         {
 3             List<List<int>>[] ret = new List<List<int>>[2];
 4             ret[0] = new List<List<int>>();
 5             ret[1] = new List<List<int>>();
 6             int new_index = 0;
 7             int curr_index = 0;
 8 
 9             for (int i = 1; i <= n; i++)
10             {
11                 ret[curr_index].Add(new List<int>{ i });
12             }
13 
14             for (int i = 2; i <= k; i++)
15             {
16                 new_index = (curr_index + 1) % 2;
17 
18                 foreach (var item in ret[curr_index])
19                 {
20                     int max = item[item.Count - 1];
21                     for (int j = max + 1; j <= n; j++)
22                     {
23                         item.Add(j);
24                         List<int> temp = new List<int>(item);
25                         ret[new_index].Add(temp);
26                         item.RemoveAt(item.Count - 1);
27                     }
28                 }
29                 ret[curr_index].Clear();
30                 curr_index = new_index;
31             }
32 
33             return ret[new_index];
34         }

代码分析：

　　算法很简单，建立两个List<List<int>>集合，往前一个List添加比最后一个元素大的值，存放到新的List中。

　　首先往List 1，插入只有一个int的List<int>。

　　然后再List 1的基础上，往List 1中的每一个List添加比最后一个元素要大的值. (代码中max 变量存放了LIST最后一个值，最后一个值一定是最大的，然后

for (int j = max + 1; j <= n; j++).
因为例子中K = 2，所以List 2就是答案，如果K = 3, List 1 就是应该返回的List<List<int>>了。如此类推。