组合（medium难度）

本题方法和代码来源：
作者：carlsun-2
链接：https://leetcode-cn.com/problems/combinations/solution/77-zu-he-hui-su-fa-jing-dian-ti-mu-by-carlsun-2/
来源：力扣（LeetCode）

// 存放符合条件结果的集合
LinkedList<List<Integer>> result = new LinkedList<>();
// ⽤来存放符合条件结果
LinkedList<Integer> path = new LinkedList<>();

// 存放符合条件结果的集合
LinkedList<List<Integer>> result = new LinkedList<>();
// ⽤来存放符合条件结果
LinkedList<Integer> path = new LinkedList<>();
void backTracking(int n,int k, int startIndex)

if(path.size()==k){
    result.add(new LinkedList<>(path));
    return;
}

for(int i = startIndex; i <= n ;i++){
    path.add(i);// 处理节点
    backTracking(n,k,i+1);
    path.removeLast();// 回溯，撤销处理的节点
}

完整代码如下：

class Solution {
    // 存放符合条件结果的集合
    LinkedList<List<Integer>> result = new LinkedList<>();
    // ⽤来存放符合条件结果
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return result;
    }
    private void backTracking(int n,int k, int startIndex){
        if(path.size()==k){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i = startIndex; i <= n ;i++){
            path.add(i);// 处理节点
            backTracking(n,k,i+1);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            path.removeLast();// 回溯，撤销处理的节点
        }
    }
}

for(int i = startIndex; i <= n ;i++){
    path.add(i);
    backTracking(n,k,i+1);
    path.removeLast();
}

for(int i = startIndex; i <= n ;i++)

for(int i = startIndex; i <= n - (k - path.size()) + 1;i++)

优化后整体代码如下：
 

class Solution {
    // 存放符合条件结果的集合
    LinkedList<List<Integer>> result = new LinkedList<>();
    // ⽤来存放符合条件结果
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return result;
    }
    private void backTracking(int n,int k, int startIndex){
        if(path.size()==k){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i = startIndex; i <= n - (k - path.size()) + 1;i++){
            path.add(i);// 处理节点
            backTracking(n,k,i+1);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            path.removeLast();// 回溯，撤销处理的节点
        }
    }
}