A short C# DFS Recursive Solution


  • 0
    L
    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)
            {
                result.Add(lstSingle);
                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);
                lstSingleTmp.Add(i);
                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){
                curList.Add(i);
                if(k == 1 && i == n) result.Add(new List<int>(curList));
                else dfs(result, curList, k - 1, n - i);
                curList.RemoveAt(curList.Count - 1);
            }
            i++;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.