1ms Java solution (with explanation)


  • 0
    W

    A backtracking problem can usually be solved by traversing a tree, where each node represents a potential answer (in this case, each node (the variable comb) represents a combination of numbers in [1,...,n]).
    The trick to make a solution to a backtracking problem faster is to traverse as few nodes as possible in the tree.
    Thus, when you know that there aren't going to be any valid answers even if you traverse deeper, stop (in this case, the 3 "break" conditions prevent the algorithm from traversing deeper).

    public class Solution {
        
        List<List<Integer>> res;
        static final int MIN_NUM = 1;
        static final int MAX_NUM = 9;
        
        public List<List<Integer>> combinationSum3(int k, int n) {
            res = new LinkedList<List<Integer>>();
            dfs(new ArrayList<Integer>(k), k, n, MIN_NUM);
            
            return res;
        }
        
        public void dfs(List<Integer> comb, int k, int n, int startNum){
            if(n==0 && k==0){
                res.add(new ArrayList<Integer>(comb));
            } else {
                for(int num=startNum; num<=MAX_NUM; num++){
                    if(MAX_NUM-num+1 < k ||   // make sure that there're at least k nums between [startNum,startNum+1,..,9]
                        k*num+(k-1)*k/2 > n || // make sure that the min sum: num+(num+1)+..+(num+k-1) is at most n
                        MAX_NUM*k-(k-1)*k/2 < n // make sure that the max sum: 9+(9-1)+..+(9-(k-1)) is at least n
                    ) {  
                        break;
                    }
                    comb.add(num);
                    dfs(comb, k-1, n-num, num+1);
                    comb.remove((int)(comb.size()-1));
                }
            }
        }
    }
    

Log in to reply
 

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