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

Solution: in each combination, former number is smaller than the following number.  In another word, [1, 2] and [2, 1] is considered as the same combination, and only [1, 2] is required as the result in this problem.
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).  
复杂度O(n!)
类似于 Permutation那道

public class Solution {
    public ArrayList> combine(int n, int k) {
        ArrayList> result = new ArrayList>();
        ArrayList comb = new ArrayList();
        
        if(n < k)
            return result;
        int start = 1;   //start is begin from 1.
        select(n, k, start, comb, result);
        return result;
    }
    
    public void select(int n, int k, int start, ArrayList comb, ArrayList> result) {
        
        //one possible combination constructed 
        if(comb.size() == k) {
            result.add(new ArrayList(comb));  //because comb is ArrayList<> so it will not disappear from stack to stack
            return;
        }else {   
            for(int i = start; i <= n; i++) {   //try each possibility number in current position 
                comb.add(i);
                select(n, k, i+1, comb, result);  //after selecting number for current position, process next position 
                comb.remove(comb.size() - 1);  //clear the current position to try next possible number
            }
        }
    }
}

Or:

public class Solution {
    public List> combine(int n, int k) {
        List> res = new ArrayList>();
        if (n < k) {
            return res;
        }
        
        List list = new ArrayList();
        int start = 1;
        helper(res, list, n, k, start);
        return res;
    }
    
    public void helper(List> res, List list, int n, int k, int start) {
        if (list.size() == k) {
            res.add(new ArrayList(list));
            return;
        } else {
            for (int i = start; i <= n; i++) {
                list.add(i);
                helper(res, list, n, k, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}