LeetCode -- Combinations

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添加到結果集並返回。






實現代碼：

public class Solution {
    public IList> Combine(int n, int k) 
    {
        var result = new List>();
    	Do(1, n, k, new List(), ref result);
    	return result;
    }
    
    private void Do(int start, int n, int k, List current, ref List> result)
    {
    	if(current.Count == k){
    		result.Add(new List(current));
    		return;
    	}
    	
    	for(var i = start; i <=n ;i ++){
    		current.Add(i);
    		Do(i+1, n, k, current, ref result);
    		current.Remove(current.Last());
    	}
    }
}