# A short C# DFS Recursive Solution

• ``````public class Solution {
public IList<IList<int>> CombinationSum3(int k, int n)
{
List<IList<int>> result = new List<IList<int>>();
helper(new List<int>(), result, 0, k, n);
return result;
}

private void helper(IList<int> lstSingle, IList<IList<int>> result, int index, int k, int n)
{
if (k == lstSingle.Count && n == 0)
{
return;
}
if (index > k - 1) return;
int curMax = index == 0 ? 0 : lstSingle[index - 1];
for (int i = curMax + 1; i <= n && i < 10; i++)
{
List<int> lstSingleTmp = new List<int>(lstSingle);
helper(lstSingleTmp, result, index + 1, k, n - i);
}
}
}
``````

Another Solution:

``````public IList<IList<int>> CombinationSum3(int k, int n) {
IList<IList<int>> result = new List<IList<int>>();
if(k < 1 || k > 9) return result;
int max = 0, min = 0;
for(int i = 0; i < k; i++){
max += 9 - i;
min += i + 1;
}
if(max < n || min > n) return result;
dfs(result, new List<int>(), k, n);
return result;
}
private void dfs(IList<IList<int>> result, IList<int> curList, int k, int n){
int i = (curList.Count == 0 ? 0 : curList[curList.Count - 1]) + 1;
while(i < 10){
if(i > n) return;
if(k != 1 || i == n){