Recursion and DP
In Leetcode, there are many backTrack problems, some of which are good starting points.
Combination Sum, Factor Combinations, Permutations, Permutations II.
More advanced: Evaluate Division, Word Pattern II, Remove Invalid Parentheses, Basic Calculator
When solving a BT problem, pay attention to whether it’s a Permutation problem, or a Combination.
The problem here is a permutation.
A general recursive template for backtracking may look like this:
helper (parameters of given data and current recursive level) {
// Handle base cases, i.e. the last level of recursive call
if (level == lastLevel) {
record result;
return sth;
}
// Otherwise permute every possible value for this level.
for (every possible value for this level) {
helper(parameters of given data and next recursive level);
}
return sth;
}
9.2 设想有个机器人坐在X×Y网格的左上角，只能向右、向下移动。机器人从(0,0)到(X,Y) 有多少种走法？
进阶:假设有些点为“禁区”，机器人不能踏足。设计一种算法，找出一条路径，让机器人从左上 角移动到右下角。（第 68 页）
进阶：递归逆向推
Repeat: HashMap
9.3 在数组A[0...n1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数 组，元素值各不相同，编写一个方法，在数组A中找出一个魔术索引，若存在的话。 进阶 如果数组元素有重复值，又该如何处理？（第 68 页）
Solution: Binary Search
What if there exist duplicate?
综上，我们得到一般模式：先比较midIndex和midValue是否相同。然后，若两者不同，则 按如下方式递归搜索左半部分和右半部分。
左半部分：搜索索引从start到Math.min(midIndex - 1, midValue)的元素。
右半部分：搜索索引从Math.max(midIndex + 1, midValue)到end的元素。
9.4 编写一个方法，返回某集合的所有子集。（第 68 页）
解法 1：递归
9.5 编写一个方法，确定某字符串的所有排列组合。（第 68 页）
许多递归问题一样，简单构造法非常管用。假设有个字符串 ，以字符序列a 1 a 2 …a n 表示
由于将会有n!种排列组合，这种解法的时间复杂度为O(n!)，已经是最优解。
Construct in reverse order
9.6 实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）。（第 68 页）
(1) 左括号：只要左括号还没有用完，就可以插入左括号。
(2) 右括号：只要不造成语法错误，就可以插入右括号。何时会出现语法错误？如果右括号 比左括号还多，就会出现语法错误。
9.8 给定数量不限的硬币， 币值为 25 分、10 分、5 分和 1 分， 编写代码计算n分有几 种表示法。（第 69 页）
这是个递归问题， 我们要找出如何利用较早的答案（也就是子问题的答案）计算出 makeChange(n)。
9.9 设计一种算法，打印八皇后在 8×8 棋盘上的各种摆法，其中每个皇后都不同行、不同 列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对 角线。（第 69 页）
9.10 给你一堆n个箱子，箱子宽w i 、高h i 、深d i 。箱子不能翻转，将箱子堆起来时，下面 箱子的宽度、高度和深度必须大于上面的箱子。实现一个方法，搭出最高的一堆箱子，箱堆的 高度为每个箱子高度的总和。（第 69 页）
卡塔兰数