分治、回溯本质上就是一种特殊的递归，它是递归的一个细分类。

遇见题目要找重复性，重复性分为最近重复性和最优重复性。
最优重复性就是动态规划，最近重复性根据重复性如何构造，以及如何分解，就分为分治、回溯等各种办法。

分治 Divide & Conquer

分治针对递归状态树，可以将一个问题化解为多个子问题。

代码模板

  1. function divide_conquer (problem, param1, params2, ... ){
  2.   // recursion terminator
  3.   if (!problem) {
  4.     process_result
  5.     return
  6.   };
  8.   // prepare data
  9.   data = prepare_data(problem);
  10.   subprobems = split_problem(problem, data);
  12.   // conquer subproblems
  13.   subresult1 = divide_conquer(subprobems[0], p1, ...);
  14.   subresult2 = divide_conquer(subprobems[1], p1, ...);
  15.   subresult3 = divide_conquer(subprobems[2], p1, ...);
  16.   ...
  18.   // process and generate the final result
  19.   result = process_result(subresult1, subresult2, subresult3, ...);
  21.   // revert the current level states
  22. }

回溯 Backtracking

回溯法采用试错的思想，尝试分步解决一个问题。在分步解决问题的过程中，如果发现现有的分步答案不能得到有效的正确解答，它将取消上一步甚至是上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

  • 找到一个可能存在的正确答案；
  • 尝试了所有可能的分布方法后宣告该问题没有答案。

最坏情况下，回溯法会导致一次复杂度为指数时间的计算。

相关题目

Pow(x, n) （Facebook 在半年内面试常考）

子集（Facebook、字节跳动、亚马逊在半年内面试中考过）

参考链接：

牛顿迭代法原理

牛顿迭代法代码

// Pow(x, n)

// 思路1：暴力法，循环 n 次，O(n)

// 思路2：分治 O(log n)
//     pow(x, n)
//         subproblem: subresult = pow(x, n / 2)
//  merge：
//        n % 2 == 1，result = subresult * subresult * x
//         else，subresult * subresult

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  if (n === 0) return 1;

  if (n < 0) return 1 / myPow(x, -n);

  const mul = myPow(x * x, (n / 2) >> 0);

  return n % 2 ? x * mul : mul;
}

// 子集

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  const ans = [];

  const backtrack = (path, l, start) => {
    if (path.length === l) {
      ans.push(path);
      return;
    }

    for (let i = start; i < nums.length; i++) {
      backtrack(path.concat(nums[i]), l, i + 1);
    }
  }

  for (let i = 0; i <= nums.length; i++) {
    backtrack([], i, 0);
  }

  return ans;
};


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  const ans = [];

  if (!nums) return ans;

  const dfs = (nums, list, index) => {
    if (index === nums.length) {
      ans.push(list);
      return;
    }

    dfs(nums, list.slice(), index + 1);

    list.push(nums[index]);

    dfs(nums, list.slice(), index + 1);
  };

  dfs(nums, [], 0);

  return ans;
};

多数元素 （亚马逊、字节跳动、Facebook 在半年内面试中考过）

电话号码的字母组合（亚马逊在半年内面试常考）

// 多数元素

// 思路1: hashTable
// 思路2: 排序取中间值
// 思路3：抵消（栈方法降维）
// 思路4：分治

/**
 * 抵消（栈方法降维）
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  let x = 0,
      m = 0;

  for (let n of nums) {
    if(m === 0) x = n;
    m += x === n ? 1 : -1;
  }

  return x;
};

/**
 * 分治
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  return getMode(nums, 0, nums.length - 1);
};

function getMode (nums, left, right) {
  if (left === right) return nums[left];

  const mid = left + ((right - left) >> 1);

  const low = getMode(nums, left, mid),
        high = getMode(nums, mid + 1, right);

  if (low == high) return low;

  const lowCount = getCount(nums, low, left, right),
        highCount = getCount(nums, high, left, right);

  return lowCount > highCount ? low : high;
}

function getCount (nums, target, left, right) {
  let count = 0;

  for (let i = left; i <= right; i++) {
    if (nums[i] === target) count++;
  }

  return count;
}

// 电话号码的字母组合

/**
 * dfs
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits.length === 0) return [];

  const ans = [];

  const map = new Map([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz']
  ]);

  const dfs = (cur, i) => {
    if (i > digits.length - 1) {
      ans.push(cur);
      return;
    }

    const letters = map.get(digits[i]);

    for (const letter of letters) {
      dfs(cur + letter, i + 1);
    }
  }

  dfs('', 0);

  return ans;
};


/**
 * bfs
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (digits.length === 0) return [];

  const map = new Map([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz']
  ]);

  const queue = [''];

  for (let i = 0; i < digits.length; i++) {
    let size = queue.length;

    for (let j = 0; j < size; j++) {
      const cur = queue.shift();
      const letters = map.get(digits[i]);

      for (const l of letters) {
        queue.push(cur + l);
      }
    }
  }

  return queue;
};

N 皇后（字节跳动、苹果、谷歌在半年内面试中考过）

二叉树的层次遍历

// N 皇后（困难）

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  function isValid(row, col, chessBoard, n) {

    for (let i = 0; i < row; i++) {
      if (chessBoard[i][col] === 'Q') {
        return false
      }
    }

    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (chessBoard[i][j] === 'Q') {
        return false
      }
    }

    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (chessBoard[i][j] === 'Q') {
        return false
      }
    }
    return true
  }

  function transformChessBoard(chessBoard) {
    let chessBoardBack = []
    chessBoard.forEach(row => {
      let rowStr = ''
      row.forEach(value => {
        rowStr += value
      })
      chessBoardBack.push(rowStr)
    })

    return chessBoardBack
  }

  const result = [];

  function backtracing(row, chessBoard) {
    if (row === n) {
      result.push(transformChessBoard(chessBoard))
      return
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col, chessBoard, n)) {
        chessBoard[row][col] = 'Q'
        backtracing(row + 1, chessBoard)
        chessBoard[row][col] = '.'
      }
    }
  }

  const chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'));

  backtracing(0, chessBoard);

  return result
};

// 二叉树的层次遍历

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (!root) return [];

  const ans = [];

  const queue = [root];

  while (queue.length) {
    let len = queue.length;

    ans.push([]);

    while (len--) {
      const n =  queue.shift();

      ans[ans.length - 1].push(n.val);

      n.left && queue.push(n.left);
      n.right && queue.push(n.right);
    }
  }

  return ans;
};