Combinations @LeetCode

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

	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);
	}
	}

view raw Combine.java hosted with ❤ by GitHub