AC Java Solution 99% faster with explanation


  • 0
    A
    public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if(n <= 0 || k <= 0 || n < k)
            return result;
        
        //Initialize the array nums.
        //Not really required. 
        //nums is just used to explain the concept better when a generic array of say strings are used
        //index i stores the value i+1
        int[] nums = new int[n];
        
        for(int i = 0; i < n; i++)
            nums[i] = i+1;
        
        //This array stores the result for each combination
        int[] combination = new int[k];
        
        doCombine(nums, combination, 0, 0, n, k, result);
        
        return result;
    }
    
    //This recursive method will loop till level = k at which point we have a combination of length k
    //So we have a level variable to keep track of the level
    //startIndex will indicate what the next eligible index for combination will be
    //Unlike permutation, we do not have to go back to revisit the old index so, we only need to look forward 
    //from the startIndex position
    public void doCombine(int[] nums, int[] combination, int level, int startIndex, int n, int k, List<List<Integer>>result) {
        if(level == k) {
            ArrayList<Integer> combinationList = new ArrayList<Integer>();
            
            for(int i = 0; i < k; i++) {
                combinationList.add(combination[i]);    
            }
            
            result.add(combinationList);
            
            return;    
        }
        
        //Why do we cap the index location by n-k+level
        //1 2 3 4 5         n = 5   k = 3
        //For Level 0
        //index 0 can have values 1 2 3
        //i.e the indexes can be startIndex = 0, 1 and 2 [5-3+0]
        
        //For Level 1, let us say the startIndex = 1 (it can not be 0 since we only look forward)
        //index 1 can have values 2 3 4
        //i.e the indexes can be startIndex = 1, 2 and 3 [5-3+1] so StartIndex = 1 and end index = 3
        
        for(int i = startIndex; i <= (n-k+level); i++) { //remember to add <= for  i <= (n-k+level)
            combination[level] = nums[i]; // nums[i] stores i+1 in this case
            doCombine(nums, combination, level+1, i+1, n, k, result);
        }
    }    
    }

Log in to reply
 

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