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


解题思路：
                1. 求n个数中的k个数的组合，如果此组合含有n,则就是求n-1的k-1个组合，不含有n，就是n-1的k。即 combine(n, k) = combine(n-1, k -1) + combine(n-1, k);
                2. 要注意的就是n-1,k-1可能返回nil, 那么这时就要初始化n。
       

public List> combine(int n, int k) {
         List> res = new ArrayList>();
         
         if( n < k || k == 0) return res;
         
         res = combine(n-1, k-1);
         
         for(int i = 0; i < res.size(); i++){
             List tmp = res.get(i);
             tmp.add(n);
         }
         
         if(res.size() == 0){
             List tmp = new ArrayList();
             tmp.add(n);
             res.add(tmp);
         }
         
         res.addAll(combine(n-1, k));
         
         return res;
    }