题目

  1. Subsets I & II
  2. Combination Sum I & II & III
  3. Permutation I & II
  4. Palindrome Partitioning
  5. N-Queens
  6. Word Ladder
  7. Expression Expand
  8. String Permutation II

总结

  1. Traverse 给人的感觉是先解决问题前面的一部分, 再递归地去解决缩小了的问题
    1. 比如Palindrome partitioning, 当我们从头走向字符串末尾, 我们将问题变成了, 假若前面的子串划分确定好了, 并且是palindrome, 那么问题便会转化为 find all possible palindrome partitioning of s(i, s.length)
  2. divide & conquer 就是一直走, 走到问题的最后, 一小部分一小部分解决了, 然后合并小问题来解决大问题
  3. 其实
    1. 一个permutation
    2. 一个subset
    3. 一个combination sum to target
    4. 一个palindrome partitioning string
    5. 一个n-queen 方案
  4. 它们相当于一个solution, 而使用dfs, 当前的递归就相当于先解决前一小部分的问题
    1. 比如
      1. 确定其中一个permutation的第一个数
      2. 确定其中一个subset的第一个数
      3. 确定其中一个palindrome string 的第一个string
      4. 确定其中一个n-queen 方案的 第一行
    2. 那么n大小问题就会缩小为 n - 1 问题
      1. 解决当前这个permutation 的余下的位置的空缺
      2. 解决当前string余下的字母的partitioning
      3. 解决当前这个方案余下的行
  5. 一个非常非常容易错的点
    1. 尽量不用continue, 因为很容易让你的backtracking 出错
  6. 有一点容易错的是： stringbuilder 反转后要反回去，不然bactracking会出错
  7. dfs 适合找路径, bfs适合找点
  8. 另外， 通过一个点找到其余连通的点也能用dfs
  9. 记录形状可以用偏移量组成字符串
  10. 将两个具有某一相同特征的事物组合在一起， 可以根据图的连通块概念
  11. 组合类型的题目[1,2,3]， 通常递归定义是以空集（index为0）开始的结果集, 以1开始的结果集

results matching ""

    No results matching ""