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

        if (n < k)
            return null;
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (k == 1) {
            for (int i = 1; i <= n; i++) {
                ArrayList<Integer> al = new ArrayList<Integer>();
                al.add(i);
                all.add(al);
            }
            return all;
        }
        for (int i = n; i >= k; i--) {
            for (ArrayList<Integer> al : combine(i - 1, k - 1)) {
                al.add(i);
                all.add(al);
            }
        }
        return all;
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        return helper(1, n, k);
    }

    private ArrayList<ArrayList<Integer>> helper(int start, int end, int k) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> re = new ArrayList<Integer>();
        if (end - start + 1 < k || k <= 0) {
            result.add(re);
            return result;
        }
        // add all to the re
        if (end - start + 1 == k) {
            for (int i = start; i <= end; i++) {
                re.add(i);
            }
            result.add(re);
            return result;
        }
        // include start
        ArrayList<ArrayList<Integer>> tmp = helper(start + 1, end, k - 1);
        for (ArrayList<Integer> r : tmp) {
            re = new ArrayList<Integer>(r);
            re.add(0, start);
            result.add(re);
        }
        // not inclued start
        ArrayList<ArrayList<Integer>> tmp2 = helper(start + 1, end, k);
        result.addAll(tmp2);
        return result;
    }
}