77. 组合
216. 组合总和 III
17. 电话号码的字母组合
39. 组合总和
Note: 组合问题中，如果限制数量，便可以从每层循环的终止条件上做剪枝，如i <= n + 1 - (k - path.size()) 其中k - path.size() 为当前剩余需要的元素个数（k为限制的元素数量，path.size()为当前的元素数量），n为startIndex索引的最大值。如果限制一个组合内不可重复使用同一元素，那么便需要将下一层startIndex设为当前startIndex+1，否则不变。
class Solution {
private:
vector<vector<int>> ans;
vector<int> combo;
void backtrace(int n, int k, int startIdx) {
if (combo.size() == k) {
ans.push_back(combo);
return;
}
for (int i = startIdx; i <= n + 1 - (k - combo.size()); ++i) {
combo.emplace_back(i);
backtrace(n, k, i + 1);
combo.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
ans.clear();
combo.clear();
backtrace(n, k, 1);
return ans;
}
};
40. 组合总和 II
Note: 注意如果要求元素组合不可重复和组合内元素可重复（集合内本身有重复元素），那么需要将集合先排序，然后限定同层元素不可重复。这里组合总和I和II的区别在于，I是原数组无重复元素，但组合内可以重复，因此下层startIdx不+1，也不需要去重；而II是原数组有重复元素，那因此本层可能遇到重复元素，需要排序去重（是值去重，能排序就可以排序去重，不能就需要用set或者数组来记录本层访问过的值），而组合内不允许（索引）重复，因此下层startIdx要+1。
131. 分割回文串
Note: 本题优化：先行求好回文串，使用动态规划等方法，在回溯时直接取用。
93. 复原 IP 地址
78. 子集
90. 子集 II
491. 非递减子序列
Note: 注意这里非递减子序列，如果采用同层for而非每个数组代表一层的话，必须使用一个set来记录当前层某一数字是否出现过（本题不可排序！），而使用一层代表一个数字出现与否的话，则不需要，因为可以聚焦于局部（而且不需要排序因为path内部一定是有序的！），对于当前数字b，其如果等于path尾部数a，那么a有b没有和a没有b有是局部等效的（不影响前面或后面），因此必须过滤其中之一，这里选择的是b不可以以没有的身份进入下一层，在此限制条件下，不会出现a有b没有的情况。在491中，相比于原始方法需要在每一层加一个set去重，一层一个数字反而更快，但是在90中，这种方法是更慢的，因为产生了大量无效节点（相比原始方法每个节点均有效，该方法直到叶子结点才有效）。
不过，在491中，原始方法可以优化，可以用数组去取代set，此时耗时和空间都降低很多，因此还是偏向于使用原始方法，简单明了。
在子集II中，无论使用前后比较去重（比较nums[i]和nums[i-1]）还是set去重，都需要对原数组排序，因为去重是让同一父节点下子节点不重复，如果不排序原数组，重复的数字可能被分到不同的节点下面，导致不同父节点下的子节点发生重复。如果排序，那么由于原数组被按照值从小到大排序，每个节点只可能将比它值大的元素作为子节点，相反，对于集合{2,1,2,2}，如果不排序，就会导致下图的问题，原因在于首层取2的节点持有了元素1并将其作为子节点。
46. 全排列
47. 全排列 II
Note: 注意全排列和全组合不一样的一点：只需要大小等于数组大小的序列，没有startIdx，每层for循环均从0开始，并且使用used数组来记录for当前索引是否在上层用过。在全排列II中，原数组存在重复元素，因此需要本层去重，使用条件i > 0 && nums[i] == nums[i - 1] && !used[i - 1]来判断是否需要跳过该次for循环（本层去重）。因为对于连续的两个数，如果他们相同并且前一个数在上层未访问，那么其在本层一定被访问过，后一个数不应该被重复访问。相反如果连续两个数不同，或者前一个数被上层访问了，那么后一个数都是可以在本层访问的。实际上，数层去重和树枝去重均可，但数层去重有利于提早剪枝。
332. 重新安排行程
Note: 虽然本题是困难题，但是主要困难在数据结构的选取，这里采用
unordered_map<出发机场, map<到达机场，次数>> routes;
来存放输入的数据，不仅直观，而且方便读取写入，不会产生问题。这里其实主要使用了深度优先搜索算法，对于给定的起始地，寻找所有可能的目的地作为下一层节点，搜索一次，将目的地加入路径path中并且--routes[出发地][起始地]，不断向下搜索，直到路径长度=票数量（目的地数量）+1（起始地数量），即得到结果。
51. N 皇后
37. 解数独
Note: 解数独是二维回溯，backtrace需要两层循环，当然也可以使用状态压缩来加快运算。