Easy Java dfs, 1ms


  • 0
    V
    public class Solution 
    {
        List<List<Integer>> toRet;
        public List<List<Integer>> combinationSum3(int k, int n) 
        {
            toRet = new ArrayList<List<Integer>>();
            if(n <= k)
                return toRet;
            dfs(0, -1, 0, k, n, new ArrayList<Integer>());
            return toRet;
        }
        void dfs(int currSum, int currInd, int currLvl, int k, int n, List<Integer> myList)
        {
            if(currLvl == k)
            {
                if(currSum == n)
                {
                    List<Integer> temp = new ArrayList<Integer>(myList);
                    toRet.add(temp);
                }
                return;
            }
            for(int i = currInd + 1; i < 9; i++)
            {
                if(currSum + i + 1 > n)
                    break;
                myList.add(i + 1);
                dfs(currSum + i + 1, i, currLvl + 1, k, n, myList);
                myList.remove(myList.size() - 1);
            }
        }
    }

Log in to reply
 

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