Anyway to improve this AC java recursive algorithm?


  • 0
    F
    public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res= new LinkedList<List<Integer>>();
    /*handle special case when k > 9 or n > 9k - k*(k-2)/2 or n < k, note: 9k - k*(k-2)/2 means the maximum value we can get, i.e, k = 1, maximum = 1, k = 2, maximum = 9 + 8 = 17, k = 3, maximum = 9 + 8 + 7 = 3 * 9 - 1 - 2...*/
        if(k > 9 || n > 9*k - k*(k-1)/2 || n < k) {return res;}
    /*handle special case when k == 1*/
        if(k == 1){
            List<Integer> list = new LinkedList<Integer>();
            list.add(n);
            res.add(list);
            return res;
        }
        helper(res,new LinkedList<Integer>(),k,n,1);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> cur_list, int k, int n, int start){
        if(cur_list.size() == k){
            if(n == 0){
                List<Integer> new_list = new LinkedList<Integer>(cur_list);
                res.add(new_list);
            }
            return;
        }
        for(int i = start; i < 10; i++){
            if(i <= n){
                cur_list.add(i);
                helper(res,cur_list,k,n - i,i+1);
                cur_list.remove(cur_list.size() - 1);
            }else{
                return;
            }
        }
    }
    

    }


Log in to reply
 

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