理论基础

回溯是和递归相辅相成的，回溯的本质就是暴力解法，用于那些多层for循环无法解决的问题，比如组合、切割、集合等，回溯也有三个步骤

1. 确定回溯函数的参数与返回值，一般情况下返回值为void，参数中一般有一个startIndex
2. 确定终止条件
3. 单层逻辑，一般是for循环里带递归，并且要有回溯

77. 组合

77. 组合 - 力扣（LeetCode）
组合是典型的递归问题，参见递归的三步骤

class Solution {
    public List<List<Integer>> result = new ArrayList<>();
    public List<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            //不能直接add path，因为path后面还会改变，所以要新建一个
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i=startIndex; i<=n; i++) {
            path.add(i);
            backtracking(n, k, i+1);
            //回溯，将最后一个移除
            path.removeLast();
        }
    }
}

对于本题还可以再优化，这里for循环里i是从startIndex到n，但实际情况是不需要到n，只需要到n-(k-path.size())+1