2020-05-02 77. Combinations Med

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input:n = 4, k = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]

这里有个比较细节但是能提升性能的地方，在代码中用(1)标出

一般会想到的条件是i<=n

以n=5,k=3为例

如果条件是i<=n，则回溯树长这样:

 i <= n - k + 1的时候则是：

假如k很接近n，如果用i<=n就会浪费很多次遍历。比如n=k=5，

i<=n+k-1的话，只需遍历一次。i<=n则遍历很多次，已经不是一个数量级耗时了

class Solution {

    List<List<Integer>> res = new LinkedList<>();

    ArrayList<Integer> cur = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {

        doCombine(n, k, 1);

        return res;

    }

    private void doCombine(int n, int k, int start) {

        if (0 == k) {

            res.add(new ArrayList<>(cur));

            return;

        }

        for (int i = start; i <= n - k + 1; i++) {                   //          ---------------- (1)

            cur.add(i);

            doCombine(n, k - 1, i + 1);

            cur.remove(cur.size() - 1);

        }

    }

}

最后，有没有大佬能把准确的时间复杂度公式算出来？还请不吝赐教~