問(wèn)題：
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],
]

依照我們做排列的思路寫(xiě)代碼便可：
1、按順序從小到達(dá)排列n個(gè)數(shù)。
2、從中取出k個(gè)數(shù)，其實(shí)就是先取出1個(gè) （k種可能），然后從剩下的k⑴個(gè)中再取出1個(gè)（k⑴種可能），以此類(lèi)推。

為了保證取出的組合不重復(fù)，我們保證下1個(gè)取出的數(shù)1定在當(dāng)前數(shù)的后面便可。
即第1個(gè)數(shù)取了1后，第2個(gè)數(shù)只能從2～n中??；第1個(gè)數(shù)取了2后，第2個(gè)數(shù)只能從3～n中取 （取了2再取1，會(huì)和取了1再取2重復(fù)）。

整體來(lái)說(shuō)結(jié)果就是將第1位為1的所有排列取完后，才開(kāi)始取所有第1位為2的排列，順次類(lèi)推。

代碼示例：

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> rst = new ArrayList<>();

        if (n < 0 || k < 0 || n < k) {
            return rst;
        }

        //初始化數(shù)組
        int[] nInts = new int[n];
        for (int i = 0; i < n; ++i) {
            nInts[i] = i+1;
        }

        List<Integer> curr = new ArrayList<>();
        for (int i = 0; i <= n-k; ++i) {
            //順次安排好第1位，這個(gè)實(shí)際上是基于深度優(yōu)先的迭代
            combineInner(rst, nInts, i, curr, k);
        }

        return rst;
    }

    private void combineInner(List<List<Integer>> rst, int[] nInts, int next, List<Integer> curr, int sz) {
        //將當(dāng)前數(shù)加入結(jié)果隊(duì)列
        List<Integer> newList = new ArrayList<>(curr);
        newList.add(nInts[next]);

        //判斷長(zhǎng)度是不是滿(mǎn)足了條件
        if (newList.size() == sz) {
            rst.add(newList);
            return;
        }

        //順次加入當(dāng)前位以后的數(shù)
        for (int i = next+1; i <= nInts.length - (sz - newList.size()); ++i) {
            combineInner(rst, nInts, i, newList, sz);
        }
    }
}