Anyone able to improve this recursive solution?I think it's kind of slow but it works


  • 0
    F
    public class Solution {`enter code here`
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
    /*handle special case when n == 1 or k == 1 or k > n*/
        if(k > n) {return res;}
        if(n == 1){
            List<Integer> list = new LinkedList<Integer>();
            list.add(1);
            res.add(list);
            return res;
        }
        if(k == 1){
            for(int i = 1; i <= n; i++){
                List<Integer> list = new LinkedList<Integer>();
                list.add(i);
                res.add(list);
            }
            return res;
        }
    /*use helper function to do recursive calls*/
        helper(res,new LinkedList<Integer>(),n,k,1);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> cur_list, int n, int k, int start){
    /*check if size of the current list is equal to k, if it is, add it to result then return, else keep adding element*/
        if(cur_list.size() == k){
            List<Integer> new_list = new LinkedList<Integer>(cur_list);
            res.add(new_list);
            return;
        }
    /*adding element to current list, to avoid adding same value, every time we do recursive call, start = i + 1, then we remove elements of current list at the end of the iteration*/
        for(int i = start; i <= n; i++){
            cur_list.add(i);
            helper(res,cur_list,n,k,i + 1);
            cur_list.remove(cur_list.size() - 1);
        }
    }
    

    }


Log in to reply
 

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