回溯分为组合篇、排列篇、分割篇和子集篇。
回溯具有高度模板化，以下为模版代码：
组合问题分为以下3种：
- 1 数组中可选择的元素可以至多可以选择一次
- 1 模版题；
- 2 循环中的下一个迭代的起始索引+1
- 2 数组中可选择的元素可以重复无限制选取
- 1 在模版题的基础上；
- 2 函数入口多增加越界判断（否则会无限循环）；
- 3 循环中的下一个迭代的起始索引不变。
- 3 数组中可选择的元素可以至多先选择一次，同时返回结果没有重复子数组。
- 1 在模版题目的基础上
- 2 先对数组进行排序，使数组中重复元素挨着
- 3 增加used数组进行去重，nums[i-1] = num[i]则说明重复（该重复为同层之间的重复，同一个树枝中允许重复）
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过 // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
1 组合问题
题目类型一。
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
剪枝版本：
- k – path.size(): 还需要加入的节点数量
- n – (k – path.size()) + 1 : 下标需要在索引左边才能加入足够多的节点数量
2 组合总和
题目类型一。
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
1 模版题；
2 循环中的下一个迭代的起始索引+1
优化版本：
- 1 candidates数组需要排序
- 2 for循环中total+candidates <= target
3 组合总和III
题目类型二。
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
题目类型二。
1 在模版题的基础上；
2 函数入口多增加越界判断（否则会无限循环）；
3 循环中的下一个迭代的起始索引不变。
优化版本：
- 1 数组需要排序（已经有序）
- 2 for循环中total+candidates <= target
4 组合总和II
题目类型三。
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
- 1 在模版题目的基础上
- 2 先对数组进行排序，使数组中重复元素挨着
- 3 增加used数组进行去重，nums[i-1] = num[i]则说明重复（该重复为同层之间的重复，同一个树枝中允许重复）
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过 // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
直接给出优化版本。
