Best solution! Beats 90% Java Iterative and recursive solution


  • 0

    // The property of all combinations for k out of n is that:
    // the least number of some combinations can be 1;
    // the least number of some combinations can be 2;
    // ...
    // To sum up, the least number of every combinations cann't be greater than n-k+1;
    // In fact, the ith least number of every combinations cann't be greater than n-k+i;

    // My solution idea:
    // All combinations for k out of n can be grouped into n-k+1 groups:
    // group1: the least number of every combinations in this group is 1;
    // group2: the least number of every combinations in this group is 2;
    // ......
    // group n-k+1: the least number of every combinations in this group is n-k+1;

    // So combinations for k out of n can be solved in k grouping steps:
    // Grouping Step1:
    // Create group1.1 that just has number 1 as least number
    // Create group1.2 that just has number 2 as least number
    //....
    // Create group 1.n-k+1 that just has number n-k+1 as least number
    // add All groups above into result1, we will retrieve them in Step2
    // Grouping Step2:
    // Retrieve group1.1 from result1
    // Copy group1.1 as group2.1.1 and add (group1.2_lastElement + 1) as 2th least number
    // Copy group1.1 as group2.1.2 and add (group1.2_lastElement + 2) as 2th least number
    //....
    // Copy group1.1 as group2.1.n-k+2 and add (n-k+2) as 2th least number
    // add All groups above into result2, we will retrieve them in Step3
    // Retrieve group1.2 from result1
    // Copy group1.2 as group2.2.1 and add (group1.2_lastElement + 1) as 2th least number
    // Copy group1.2 as group2.2.2 and add (group1.2_lastElement + 2) as 2th least number
    //....
    // Copy group1.2 as group2.2.n-k+2 and add (n-k+2) as 2th least number
    // add All groups above into result2, we will retrieve them in Step3
    // Retrieve group1.3 from result ... until exhaust
    // Grouping Step3: // Retrieve groups from result2 ... update them to have 3th least number
    // ...
    // Grouping Stepk: // Retrieve groups from result k-1 ... update them to have kth least number
    // Return result k

    //Iterative version: 
    public static List<List<Integer>> combine(int n, int k) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	result.add(new ArrayList<Integer>());
    	//It takes k grouping steps:
    	for (int i = 1; i <= k; i++) {
    		List<List<Integer>> tmp = new ArrayList<List<Integer>>();
    		for (List<Integer> list : result) {
    			int nextElement=1;//For step 1
    			if(list.size()>0) nextElement=list.get(list.size() - 1)+1; //For step >1
    			for (;nextElement <= n - k + i; nextElement++) {
    				List<Integer> newList = new ArrayList<Integer>(list);
    				newList.add(nextElement);
    				tmp.add(newList);
    			}
    		}
    		result = tmp;
    	}
    	return result;
    }
    //Recursive version: 
    public static List<List<Integer>> combineRecursive(int n, int k) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	result.add(new ArrayList<Integer>());
    	result = combineHelper(n, k, 1, result);
    	return result;
    }
    public static List<List<Integer>> combineHelper(int n, int k, int step, List<List<Integer>> result) {
    	List<List<Integer>> tmp = new ArrayList<List<Integer>>();
    		for (List<Integer> list : result) {
    			int nextElement=1;//For step 1
    			if(list.size()>0) nextElement=list.get(list.size() - 1)+1; //For step >1
    			for (;nextElement <= n - k + step; nextElement++) {
    				List<Integer> newList = new ArrayList<Integer>(list);
    				newList.add(nextElement);
    				tmp.add(newList);
    			}
    		}
    		if(step+1>k) return tmp;
    		return combineHelper(n, k, step+1, tmp);
    }

Log in to reply
 

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