模板

分治

模板

  1. private static int divide_conquer(Problem problem,):
  2.     # recursion terminator
  3.     if (problem == NULL){
  4.         int res = process_last_result();
  5.         return res;
  6.     }
  8.     int subproblem = split_problem(problem)
  10.     # conquer subproblems
  11.     int res0 = divide_conquer(subproblem[0])
  12.     int res1 = self.divide_conquer(subproblem[1])
  14.     # process and generate the final result
  15.     int result = process_result(res0,res1)
  17.     return result;
  18. }

回溯

image.png

模板

  1. void backtracking(参数) {
  2.     if (终止条件) {
  3.         存放结果;
  4.         return;
  5.     }
  7.     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
  8.         处理节点;
  9.         backtracking(路径，选择列表); // 递归
  10.         回溯，撤销处理结果
  11.     }
  12. }

50. Pow(x, n)

78. 子集

169. 多数元素

17. 电话号码的字母组合

51. N 皇后

面试题 08.12. 八皇后