77. Combinations

问题
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

回溯，构建搜索树。
子节点取出的数值应大于父节点中取出的数值。
直到树高度达到k后返回。

返回时，要new一个List，将原有list传入。
否则添加到ans的值只是list的内存地址。
ArrayList换成LinkedList可以优化一些速度，因为可以直接removeLast。（22ms -> 16ms）
i的范围限制在start到n-k+1，后面的限制容易被忽略，可以大幅度减枝，优化速度。（16ms -> 1ms）

class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        backTrack(new LinkedList(),1,n,k);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list, int start, int n, int k){
        if (k == 0){
            ans.add(new ArrayList(list));
            return;
        }

        for (int i = start; i <= n-k+1; i++){
            list.add(i);
            backTrack(list, i+1, n, k-1);
            list.removeLast();
        }
    }
}