LeetCode -- Combinations
题目描述：
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],
]
在小于等于n的数构成的子集中，找到长度为k的子集。例如小于3的子集有{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}，而当k=2时，符合条件的子集为[{1,2},{2,3},{1,3}]。
已知k的取值范围是[1,n]。
思路：
对[1,n]每个元素进行回溯。
每次添加当前元素i并进入新过程后还原状态（删除i）。
如果当前集合长度等于k添加到结果集并返回。
实现代码：
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],
]
在小于等于n的数构成的子集中，找到长度为k的子集。例如小于3的子集有{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}，而当k=2时，符合条件的子集为[{1,2},{2,3},{1,3}]。
已知k的取值范围是[1,n]。
思路：
对[1,n]每个元素进行回溯。
每次添加当前元素i并进入新过程后还原状态（删除i）。
如果当前集合长度等于k添加到结果集并返回。
实现代码：
public class Solution {
public IList<IList<int>> Combine(int n, int k)
{
var result = new List<IList<int>>();
Do(1, n, k, new List<int>(), ref result);
return result;
}
private void Do(int start, int n, int k, List<int> current, ref List<IList<int>> result)
{
if(current.Count == k){
result.Add(new List<int>(current));
return;
}
for(var i = start; i <=n ;i ++){
current.Add(i);
Do(i+1, n, k, current, ref result);
current.Remove(current.Last());
}
}
}