backtracking（回溯法）是一类递归算法，通常用于解决某类问题：要求找出答案空间中符合某种特定要求的答案，比如eight queens puzzle（将国际象棋的八个皇后排布在8x8的棋盘中，使她们不能互相威胁）。回溯法会增量性地找寻答案，每次只构建答案的一部分，在构建的过程中如果意识到答案不符合要求，会立刻将这一部分答案及它的所有子答案抛弃，以提高效率。
回溯法的核心模型是一个决策树，每个节点的子节点代表该节点的选项。从根节点出发，作出某种选择达到节点A，随后会面临节点A的选项，重复这个过程直到达到叶节点。如果途中发现某节点B的状态已经不符合要求，那么弃掉以B为根节点的子决策树。
到达叶节点时，判断其是否符合问题要求，然后根据情况作相应处理（如将符合要求的叶节点加入一个list）。叶节点没有子节点，因此回溯到上一个访问过的节点，以尝试其他选择。当我们最终回溯到根节点，且已经穷尽了根节点的所有选择时，算法结束。
在上图的决策树中，用good和bad分别代表符合和不符合要求的叶节点。回溯法的遍历过程是这样的：
从Root开始，有A和B两个选项。选择A。
从A开始，有C和D两个选项。选择C。
C不符合要求，回溯到A。
A处的剩余选项为D。选择D。
D不符合要求，回溯到A。
A的选项已穷尽，回溯到Root。
Root处的剩余选项为B。选择B。
从B开始，有E和F两个选项。选择E。
E符合要求，将其加入某个list，回溯到B。
B出的剩余选项为F。选择F。
F不符合要求。回溯到B。
B的选项已穷尽，回溯到Root。
Root的选项已穷尽。结束。
本文给出leetcode上数组排列组合问题的回溯法解答。这些问题大多为“返回某数组/字符串的所有排列/组合”类型，没有提出明确的要求来筛选叶节点。看起来，似乎简单地使用回溯法遍历决策树即可，但是在实现中会遇到一些棘手的小问题，比如每一个选项如何定义，如何记录某一个节点上已经选择过的选项等。学习回溯法时，可以先从这些问题开始熟悉回溯法的套路，熟练后再去解决更复杂的问题。
问题集subsets: 给出一个不含重复元素的数组，返回它的所有子集；
subsets w/ duplicates: 给出一个含有重复元素的数组，返回它的所有子集，不准重复；
permutations: 给出一个不含重复元素的数组，返回它的所有排列；
permutations w/ duplicates:给出一个含有重复元素的数组，返回它的所有排列，不准重复；
combination sum: 给出一个整数数组及整数target，返回和为target的所有组合，每个元素可以使用无穷多次；
combination sum -- cannot use same element twice: 给出一个整数数组及整数target，返回和为target的所有组合，每个元素只能使用一次；
palindrome partition: 给出一个String，返回它的所有分割，使分割后的每一个元素都是回文。
决策树决策树的设计是回溯法的关键。对于排列组合问题，这一步的本质是将intuitional的想法映射到解题空间，变化为决策树每一个节点的选项。
注意，决策树并不是一个具体存在的数据结构。在回溯法中，决策树代表方法递归调用的方式和顺序，每一个节点的选项实际上编写在代码逻辑中，比如用一个for循环以某种逻辑遍历数组，并在每次的iteration中递归调用方法，这个过程相当于对某一个选项作出了选择。而退出到上一层方法则相当于回溯到决策树的上一个节点。
subset问题（问题1、2）以subset问题为例，给出一个数组[1,2,3,4]，手动写出所有子集的过程大家都会，那么如何将它抽象成一个具体算法并映射到决策树？
可以这么想：[1,2,3,4]中有四个元素，其子集可以有0-4个元素。设计树的每一个节点为一个子集，根为空集。在根的基础上加一个元素，就成为了有1个元素的子集，那么根有4个选项。在第一层的节点基础上再增加一个元素，就成为了有2个元素的子集，以此类推，直至第四层。