Top down dynamic programming + some fundamental math


  • 0
    E

    Assume we have k numbers summing up to n, then there must be a number m that is maximum. Then we only need to find k-1 numbers summing up to n-m. This gives us an iterative way of coding, or DP.

    The fundamental math is that m has to satisfy some boundary conditions as explained in the coding.

    Code in Java:

    private List<List<Integer>> res;
    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        helper(k, n, list);
        for(List<Integer> l : res) // reverse order because the numbers were added in descending order in helper method
            Collections.reverse(l);
        return res;
    }
    
    //recursively check all possible combinations. add into the list if end up with k=n=0
    private void helper(int k, int n, List<Integer> list) {
        if(k<0 || n<0) return;
        if(k==0 && n==0) {
            res.add(list);
            return;
        }
        int maxUpperbound = n - k*(k-1)/2; // x1+x2+...+xk = n ==> max of xk = n - (1+2+...+(k-1))
        if(maxUpperbound < k) return; // if xk < k, there is a duplicate
        maxUpperbound = maxUpperbound > 9 ? 9 : maxUpperbound;
        int minUpperbound = (2*n + (k-1)*k)/2/k; // x1+x2+...+xk = n, and assume x1<x2<...<xk, the min value for xk should be: xk + (xk-1) + (xk-2) + ... + (xk-(k-1)) = n, thus xk = (2*n + (k-1)*k)/2/k
        
        for(int i=minUpperbound; i<=maxUpperbound; i++) {
            if(list.size()>0) { 
                int min = list.get(list.size()-1);
                if(i>=min) continue; // new upperbound cannot be equal to or greater than current min value in the list
            }
            List<Integer> innerList = new ArrayList<>(list);
            innerList.add(i);
            helper(k-1, n-i, innerList);
        }
    }

Log in to reply
 

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