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],
]

 For choosing number in a specific layer, we can use a iteration, e.g. in the first layer, we try 1-5.  While for step in another layer, we can use recursive call.  Parameters we need for a recursive call are the current combination, the combination result set, the n, the k, and the start point of iteration (e.g. if we chose 1 for the first position, start point of 2nd position is 2; while if we chose 2 for the first position, start point of second position is 3).  
Code from http://blog.csdn.net/u010500263/article/details/18435495

public ArrayList<ArrayList<Integer>> combine(int n, int k) {

        ArrayList<ArrayList<Integer>> combSet = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> comb = new ArrayList<Integer>();

        

        if(n<k) return combSet;

        helper(n, k, combSet, comb, 1);

        return combSet;

    }

    

    public void helper(int n, int k, ArrayList<ArrayList<Integer>> combSet, ArrayList<Integer> comb, int start){

        // one possible combinition constructured

        if(comb.size() == k){

            combSet.add(new ArrayList<Integer> (comb));

            return;

        }

        

        else{

            for(int i=start; i<=n; i++){// try each possibility number in current position

                comb.add(i);

                helper(n, k, combSet, comb, i+1); // after selecting number for current position, process next position

                comb.remove(comb.size()-1); // clear the current position to try next possible number

            }

        }

    }

Code from http://www.darrensunny.me/leetcode-combinations/

public ArrayList<ArrayList<Integer>> combine(int n, int k) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (n == 0 || k == 0)

            return result;

        recursiveCombine(n, k, 0, new Stack<Integer>(), result);

        return result;

    }

    /**

     * Recursive method for obtaining a list of combinations

     * @param n selection range [1...n]

     * @param k the number of selections needed

     * @param last last selection

     * @param current a stack containing current combination

     * @param result the list to record all combinations

     */

    private void recursiveCombine(int n, int k, int last, Stack<Integer> current,

                                  ArrayList<ArrayList<Integer>> result) {

        // No more selection is needed; put the current combination into result

        if (k == 0) {

            result.add(new ArrayList<Integer>(current));

            return;

        }

        // Separately add a number after the last selection, and work recursively

        for (int i = last+1; i <= n; i++) {

            current.push(i);

            recursiveCombine(n, k-1, i, current, result);

            current.pop();

        }

    }

Iterative Version from http://gongxuns.blogspot.com/2012/12/leetcodecombinations.html

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(k==0) return res;
        res.add(new ArrayList<Integer>());
        for(int i=0;i<k;i++){
             ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
             for(ArrayList<Integer> temp:res){
                int a=0;
                if(temp.size()>0)
                    a=temp.get(temp.size()-1);
                for(int j=a+1;j<=n-k+1+i;j++){
                    ArrayList<Integer> b= new ArrayList<Integer>(temp);
                    b.add(j);
                    prev.add(b);
                }
             }
            res = new ArrayList<ArrayList<Integer>>(prev);
        }
        return res;
    }

Read full article from [leet code] Combinations - 伪技回忆录 - 博客频道 - CSDN.NET