回溯问题通用模板：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
组合问题剪枝优化
在1-n数中找到所有大小为k的组合，leetcode：77https://leetcode.cn/problems/combinations/
解法：
class Solution { List<List<Integer>> result; LinkedList<Integer> path; public List<List<Integer>> combine(int n, int k) { result = new ArrayList<>(); path = new LinkedList<>(); traceback(n,k,1); return result; } public void traceback(int n, int k,int startIndex) { //递归终止条件，相当于到达叶节点，path大小达到说明此时得到了一个目标组合 if(path.size() == k) { result.add(new ArrayList<>(path)); return; } for(int i = startIndex;i <= n;i++) { path.add(i);//做选择 traceback(n,k,i+1);//把该选择移除出选择列表 path.removeLast();//撤销选择 } } }
组合问题剪枝优化
可考虑的情况：做完当前选择后剩下的选择列表大小 >= 达到大小k还需选择的元素数
例子：n = 4 k = 4 此时startIndex = 2，已有列表大小path.size()为1，加入当前元素后为path.size()+1为2，剩下的选择列表大小为n - startIndex,还需的元素数为k - (path.size() + 1)
n - startIndex >= k - (path.size() + 1) 则startIndex <= n - k + path.size() + 1 (+1容易被漏掉)