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

解题思路为from back to start，从n开始考虑。 若combination含n，则剩下的元素为combine(n-1,k-1)；若不含n，则combination为combine(n-1,k) 因此：

combine(n,k) = combine(n-1,k-1) + combine(n-1,k)。

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        if(k > n || k == 0) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = combine(n-1, k-1);
        if(res.size() == 0) {
            // k == 1
            List<Integer> comb = new ArrayList<Integer>();
            comb.add(n);
            res.add(comb);
        } else {
            for(List<Integer> comb : res) {
                comb.add(n);
            }
        }
        res.addAll(combine(n-1, k));
        return res;
    }
}