回溯之组合

来自百度百科的解释：回溯，计算机算法，回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。
常见的回溯问题有组合、排列、子集、分割和棋盘问题等。下面给出回溯算法的模板。

private void backtracking(参数1,参数2,...){
	if(递归终止条件){
		收集结果;
		return;
	}
	for(遍历集合){
		处理;
		backtracking(参数1,参数2,...); // 递归;
		回溯;
	}
}

组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例 1:
输入: n = 4, k = 2
输出:
[
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
]

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }
    void backtracking(int n, int k, int startIndex){
    	// 递归终止条件
        if(path.size() == k){
            ans.add(new ArrayList<>(path));
            return;
        }
        // for循环遍历集合，这里的集合为[1, 2, 3, ..., n]
        for(int i = startIndex;i <= n;i++){
        	// 处理
            path.add(i);
            // 递归
            backtracking(n, k, i + 1);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}

        根据上述示例，详细说明上述代码的执行过程。首先定义收集所有组合的ans集合，定义一个集合path用于收集某个组合，如果符合条件，将其放入ans集合中。combine调用backtracking方法，最后返回ans集合。接下来，详细说明backtracking的执行过程。
        path为空，不符合if条件，进入for循环，i = startIndex = 1。将1放入集合path中，path为[1]。递归进入下一个backtracking中。path长度为1，不满足if，此时startIndex为2，i从2开始，将2加入path中，此时path为[1, 2]，递归进入下一个backtracking中，满足if条件要求的path长度为2，将[1,2]放入ans集合中，并返回。返回到上一个backtracking中，执行回溯，将path最后一个元素2移除，path为[1]。继续执行for循环，刚开始startIndex为2，i从2开始，现在i++后，i等于3，将3放入path集合中，path为[1, 3]。递归进入下一个backtracking中，此时path长度为2，满足if要求的条件，将[1, 3]放入ans集合中，返回到上一个backtracking，执行回溯条件，将元素3从path中移除，path为[1]。继续执行for循环，i为4，将元素4放入path集合中，path为[1, 4]，递归进入下一个backtracking中，此时path长度为2，满足if条件，将[1, 4]放入ans中，并返回到上一个backtracking，将4从path中移除。此时for循环遍历完成，backtracking执行完成，返回最开始的trackbacking，将元素1从集合中移除。path为空。
        继续执行for循环，i++后，i为2，将元素2加入path中，此时path为[2]。进入下一个backtracking中，startIndex为3，将元素3加入path中，path为[2, 3]，递归进入下一个backtracking中，满足if条件，将[2, 3]加入ans集合中，递归返回上一个backtracking，将元素3从path集合中移除，path为[2]。i++，i为4，将元素4放入path中，path为[2, 4]。递归进入下一个backtracking中，path满足if条件，将[2, 4]放入ans集合中，并返回上一个backtracking，将4从path中移除，此时for循环遍历完成，递归返回最初的backtracking，将元素2从path中移除。
        继续执行for循环，将元素3加入到path中，path为[3]，递归进入下一个backtracking，startIndex为4，因此i等于4，将元素4加入到path中，此时path为[3, 4]，递归进入下一个backtracking中，满足if条件，将[3, 4]加入ans集合，递归返回上一个backtracking，将元素4从path中移除，path为[3]，此时for循环遍历结束，返回到最初的backtracking中，将元素3从path集合中移除，path为空。
        继续执行for循环，将元素4加入到path中，path为[4]，递归进入下一个backtracking，此时startIndex为5，大于4，不进入for循环，递归返回最初的for循环，i++，大于4，最初backtracking方法的for循环执行结束，返回到combine方法中，并返回ans。
        在上述代码中，backtracking方法中传入startIndex参数，用于标记下一轮for循环应该从哪个元素开始遍历。还可以发现在最初for循环遍历到元素4时，起始没有必要继续递归下去，也就是说集合中剩余元素小于题目要求的组合数k减去path的长度时，可以直接返回，这就是剪枝操作，去掉不必要的遍历。

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }
    void backtracking(int n, int k, int startIndex){
        // 剪枝
        if(n - startIndex + 1 < k - path.size()){
            return;
        }
    	// 递归终止条件
        if(path.size() == k){
            ans.add(new ArrayList<>(path));
            return;
        }
        // for循环遍历集合，这里的集合为[1, 2, 3, ..., n]
        for(int i = startIndex;i <= n;i++){
        	// 处理
            path.add(i);
            // 递归
            backtracking(n, k, i + 1);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}