Combinations @leetcode

Combine.java

package leetcode.combinations;
import java.util.ArrayList;


public class Combine {
	public static void main(String args[]) {
		System.out.println(combine(4,2));
	}
	
	/**
	 * @date Feb 10, 2014
	 * 
	 * Solution2:Recursive (same as subsets)
	 * Difference: only list.size == k, output the result
	 * 
	 */
	public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		combineHelper(result, list, n, k, 1);
		return result;
	}
	
	
	private static void combineHelper(ArrayList<ArrayList<Integer>> result,
			ArrayList<Integer> list, int n, int k, int position) {
		if (list.size() == k) {
			result.add(new ArrayList<Integer>(list));
			return;
		}
		
		for(int i=position; i<=n; i++) {
			list.add(i);
			combineHelper(result, list, n, k, i+1);
			list.remove(list.size() - 1);
		}	
	}


	/**
	 * Solution1: Iterative
	 * eg: combine(6,3)
	 * Fill in k element like [1,2,3] and then, this is one result, then go depth, [1,2,4] until [1,2,6]
	 * [1,2,7]which will not meet a[i]-i <= n-k+1. then it changed to [1,3,7] ,next loop, it go back to normal [1,3,4]
	 *  
	 * Most important condition
	 * 1. a[i] < a[i+1]  --> make no duplicate 
	 * 1. a[i]-i <= n-k+1; which means a[0] can't large than 4. if so, a[0]=5, a[1]=6, a[2]=? n=6. Important condition! 
	 */
    public static ArrayList<ArrayList<Integer>> combine1(int n, int k) {
    	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    	
    	int i = 0;
    	int[] a = new int[k];
    	a[i] = 1;
    	while(true) {
    		if (a[i] - i <= n - k + 1) {  // could go depth!
    			if (i == k - 1) { // a is full -- find a result 
    				combine1Helper(result, a);
    				a[i]++;
    			} else { //not full
    				i++;
    				a[i] = a[i-1] + 1;
    			}
    		} else {  // stop or go back
    			if (i == 0) {
    				return result;
    			} else {
    				a[--i] ++;
    			}
    		}
    	}
    }
    
    
    private static void combine1Helper(ArrayList<ArrayList<Integer>> result, int[] a) {
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	for(int x: a) {
    		list.add(x);
    	}
    	result.add(list); 
	}


}