LeetCode -- Combination Sum III

LeetCode -- Combination Sum III

題目描述：


Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.


Ensure that numbers within the set are sorted in ascending order.




Example 1:


Input: k = 3, n = 7


Output:


[[1,2,4]]


Example 2:


Input: k = 3, n = 9


Output:


[[1,2,6], [1,3,5], [2,3,4]]




就是從1到9構成的數組{1,2,3,4,5,6,7,8,9}中，找到一種組合，包含K個元素，和為n。


思路：
是一個典型的回溯問題，也算是問題：從數組nums中找到所有和為n的組合情況的子問題。
運用回溯模型直接解即可。 在遍歷過程中，只需要收集只有k個元素的組合。






實現代碼：

public class Solution {
    public IList> CombinationSum3(int k, int n) 
    {
       	var result = new List>();
    	Find(1, n, k, new List(), ref result);
    	return result;
    }


private void Find(int start, int target, int k, IList current, ref List> result)
{
	if(current.Count > k || target < 0)
	{
		return;
	}
	
	if(target == 0)
	{
		if(current.Count == k){
			result.Add(new List(current));
		}
		//Console.WriteLine(current);
		return;
	}
	
	for(var i = start; i < 10; i++)
	{
		current.Add(i);
		Find(i + 1, target - i, k, current,ref result);
		current.RemoveAt(current.Count-1);
	}
}


}