何为回溯？

回溯算法又叫作回溯搜索算法，简称回溯法，是一种搜索的方式（本质为穷举搜索）。回溯是递归的“副产品，有递归过程则常有回溯过程，回溯函数就是递归函数。

回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的问题都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（一棵N叉树）。

回溯法模板。

确定回溯函数的返回值和参数。
- 回溯算法中的返回值一般为void。
- 因回溯需要的参数不像二叉树的递归过程那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数就填什么参数。
确定回溯函数的终止条件。
- 既然为树形结构，那么遍历树形结构就一定要有终止条件，所以回溯也要有终止条件。
- 一般来说搜索到了叶子节点，也就找到了满足条件的一个答案，把这个答案存放起来，并结束本层递归。

//回溯函数终止条件伪代码：
if (终止条件) {
	存放结果；
    return;
}

确定回溯搜索的遍历过程。
- 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成了树的深度，见下图(可以参看Carl老哥的B站讲解，深刻理解下图):

//回溯函数遍历过程的伪代码如下：
for (选择：本层集合中的元素（树中节点孩子的数量就是集合的大小）) {
	处理节点；
    backtracking(路径， 选择列表);//递归
    回溯，撤销处理结果
}
//for 循环可以理解为横向遍历，递归过程则是纵向遍历，这样就把这棵树全遍历了。
//一般来说，搜索到叶子节点就是找到其中一个结果了。

回溯模板如下：

void backtracking(参数) {
	if (终止条件) {
		存放结果；
    	return;
    }
    for (选择：本层集合中的元素（树中节点孩子的数量就是集合的大小）) {
		处理节点；
    	backtracking(路径， 选择列表);//递归
    	回溯，撤销处理结果
	}
}

回溯经典例题：

LC77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

	//使用全局变量更加清晰，减少放在递归函数参数列表的变量
	List<List<Integer>> res = new ArrayList<>();	//存放最终结果
    LinkedList<Integer> path = new LinkedList<>();	//存放单个组合

    public List<List<Integer>> combine(int n, int k) {
       dfs(n, k, 1);
       return res;
    }
    private void dfs(int n, int k, int startIndex) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }
        //for (int i = startIndex; i <= n; i++) { //下面发生了剪枝
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            dfs(n, k, i + 1);
            //回溯
            path.removeLast();
        }
    }

组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。解集不能包含重复的组合。

	List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k <= 0 || k > 10) {
            return res;
        }

        dfs2(n,k,1);
        return res;
    }

    private void dfs2(int targetSum, int k, int startIndex) {
        if ( targetSum < 0) return;
        if (path.size() == k) {
            if (targetSum == 0) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1 ; i++) {
            targetSum -= i;
            path.add(i);
            dfs2(targetSum,k,i+1);
            targetSum += i;
            path.removeLast();
        }
    }