Accepted Java recursive solution


  • 4
    A
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            return combine(n,1,k);
        }
    
        public List<List<Integer>> combine(int n,int current,int k){
            List<List<Integer>> result = new LinkedList<List<Integer>>();
            
            if(k==0) {
                result.add(new LinkedList<Integer>());
                return result;
            }
            
            if(current>n) return result;
    
            for(List<Integer> res:combine(n,current+1,k)){
                result.add(res);
            }
            for(List<Integer> res:combine(n,current+1,k-1)){
                res.add(0,current);
                result.add(res);
            }
    
            return result;
        }
    }

  • 0
    D

    My java solution:

    public class Solution {
        List<List<Integer>> res; // result to be returned
        public List<List<Integer>> combine(int n, int k) {
            res = new LinkedList<List<Integer>>();
            if(k>n) return res;  // exit if k>n
            List<Integer> list = new LinkedList<Integer>(); // empty list used for backtracking
            helper( list, 1, n, k);
            return res;
        }
        // from, to are number ranges that will be selected in the combinations
        // k is the number of elem left to be selected
        public void helper(List<Integer> list, int from ,int to, int k){
            if(k==0) {
                res.add(new LinkedList<Integer>(list));
                return;
            }
            for(int i=from; i<=to; i++) {
                list.add(i);
                helper(list, i+1, to, k-1);
                list.remove(list.size()-1);
            }
            return;
        }
    }

Log in to reply
 

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