排列类：used以及index技巧

回溯的两个核心技巧就是：index以及used数组
我们看子集II中题解中的图：
问题是一个[1,2,2]，不可以取重复位置的元素，即可以[1,2,2]但是不能同时出现[2,1,2]，因此这一题就是一题典型的下剪枝与横剪枝结合的题目。
其中还需要注意的就是两个轴，一个是for表示了我们在阶上面的查询方向，一个是递归轴，表明了我们往深度方向上的查询方向。因此实际上也是一个后序遍历
image.png
这道题，index的主要作用就是纵向剪枝，比如我用了1那么接下来就不能再用1了，
而used主要用来横向剪枝，理解这一点需要探讨两个情况：

  1. 对于第一个函数栈帧中的for，即高度为1的三个子节点，可以想到的是，在执行完了第二颗root为2的子树之后，第三颗子树也会被执行，这显然是不行的，而index无法影响，因为index影响的是往下的，而不是for层面的
  2. 对于第二个函数栈帧中的for，也即高度为2的子节点，显然我们只能取一个2，前面的1也不能取，使用index之后确保了我们进入当前情况时，能够正确的避过1这个情况，但是一样的，在第二颗子树返回之后，又是回到了同高度，同for中的问题，index无法解决

因此，我们使用used去在同层，同for中剪枝，用index在递归链中剪枝

Used的另一种剪枝方式

除了上面说的，我们结合index使用外，单独使用used也可以横向纵向同时剪枝
比如全排列问题，这一类题目的关键在于：

  1. 元素考虑的是位置而不是数量，比如子集问题[1,2,2]，1用过之后，就再也不能考虑了，因为我们只能选择一个1，但是全排列问题[1,2,2]我们就可以选择多次1，比如两种[1,2,2] [2,2,1]是两种不同的
  2. 组合情况的相同不是子集问题的，包含的数相同，而是包含的·数以及排列位置都一样

在这种情况下used的使用其实就是：在将某个元素放置在某个位置时，其他元素的放置情况，因此used相当于将可选集合不断地缩小来进行dfs

index和used的异同

其实就是高度为2的那个1，以及第二颗数中，高度为1的那个1，二者的共同点都是，index会直接剪去这种情况。
除此之外，二者有很多相似的地方
index几乎只用于组合问题（数量相同，顺序不同也相同），排列问题used用得多，有的时候二者都需要用
不过关键还是从树上来进行区分
回溯 - 图2

填空类：map以及数组map技巧

填空类题目和组合类稍稍不同，对于填空类题目来说，往往是很多的空，因为某种限制，导致你可选空间减少，然后再进行试填回溯的。
因此实际上，填空类题目的剪枝条件，基本上是给定的，问题在于，这些空怎么组合
因此实际上又转换为了组合问题，无非就是剪枝条件变化了