个人记录-LeetCode 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],
]

依照我们做排列的思路写代码便可：
1、按顺序从小到达排列n个数。
2、从中取出k个数，其实就是先取出1个 （k种可能），然后从剩下的k⑴个中再取出1个（k⑴种可能），以此类推。

为了保证取出的组合不重复，我们保证下1个取出的数1定在当前数的后面便可。
即第1个数取了1后，第2个数只能从2～n中取；第1个数取了2后，第2个数只能从3～n中取 （取了2再取1，会和取了1再取2重复）。

整体来说结果就是将第1位为1的所有排列取完后，才开始取所有第1位为2的排列，顺次类推。

代码示例：

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;
        }

        //初始化数组
        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位，这个实际上是基于深度优先的迭代
            combineInner(rst, nInts, i, curr, k);
        }

        return rst;
    }

    private void combineInner(List<List<Integer>> rst, int[] nInts, int next, List<Integer> curr, int sz) {
        //将当前数加入结果队列
        List<Integer> newList = new ArrayList<>(curr);
        newList.add(nInts[next]);

        //判断长度是不是满足了条件
        if (newList.size() == sz) {
            rst.add(newList);
            return;
        }

        //顺次加入当前位以后的数
        for (int i = next+1; i <= nInts.length - (sz - newList.size()); ++i) {
            combineInner(rst, nInts, i, newList, sz);
        }
    }
}