Skip to content

递归与回溯

递归 Recursion

  • 将问题规模变小
  • 利用小规模问题的结果
  • 结合当前值或情况，得出最终结果

递归代码模版

function fn(n) {
  // STEP 1. 判断输入 or 状态是否非法？
  if (input/state is invalid) {
    return;
  }

  // STEP 2. 判断递归是否应该结束？
  if (match condition) {
    return some value;
  }

  // STEP 3. 将问题规模变小
  result1 = fn(n1);
  result2 = fn(n2);
  // ...

  // STEP 4. 整合结果
  return  combine(result1, result2);
}
  1. 判断当前状况是否非法，若非法，则返回。称为 完整性检查(Sanity Check)
  2. 判断是否满足递归结束条件
  3. 将问题规模缩小，递归调用
  4. 利用小规模问题的答案，结合当前数据，整合成最终答案

汉诺塔

function hano(A, B, C, n) {
  if (n > 0) {
    hano(A, C, B, n - 1);
    console.log(A + '->' + C); // move(A, C);
    hano(B, A, C, n - 1);
  }
}

91. 解码方法

var numDecodings = function(s) {
  return decode(s, s.length - 1)
};

function decode(s, index) {
  if(s[0] === '0' && index === 0) {
    return 0;
  }
  if (index <= 0) {
    return 1;
  }

  let last = s[index];
  let last2 = s[index - 1];

  let count = 0;
  if (last > '0') {
    count = decode(s, index - 1);
  }

  if (last2 === '1' || (last2 === '2' && last <='6')) {
    count += decode(s, index - 2);
  }

  return count;
}

回溯 Backtracking

  • 区别于暴力搜索：一步步向前试探，对每一步探测的情况评估，再决定是否继续。
  • 精华在于：出现非法，可以退一步或者多步，再尝试别的路径。

回溯代码模版

function fn(n) {
  // STEP 1. 判断输入 or 状态是否非法？
  if (input/state is invalid) {
    return;
  }

  // STEP 2. 判断递归是否应该结束？
  if (match condition) {
    return some value;
  }

  // 遍历所有可能的情况
  for (all possible cases) {
    // STEP 3. 尝试下一步的可能性
    solution.push(case);
    // 递归
    result = fn(m);
    // STEP 4. 回溯到上一步
    solution.pop(case);
  }
}
  1. 完整性检查(Sanity Check)
  2. 判断是否满足递归结束条件？如果是，保当前结果并返回
  3. 遍历所有可能的情况，进行递归
  4. 递归完成后，立即回溯，即取消前一步的尝试

39. 组合总和

搜索回溯思想：

  1. 以 target = 7 为 根结点 ，创建一个分支的时 做减法；
  2. 从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 candidate 数组的每个元素的值；
  3. 减到 0 或者负数的时候停止，即：结点 0 和负数结点成为叶子结点；
  4. 所有从根结点到结点 0的路径（只能从上往下，没有回路）就是要找的一个结果。
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
  let results = [];

  backtracking(candidates, target, 0, [], results);

  return results;
};

function backtracking(candidates, target, start, solution, results) {
  if (target < 0) {
    return;
  }

  if (target === 0) {
    results.push([...solution]);
    return;
  }

  for (let i = start; i < candidates.length; i++) {
    solution.push(candidates[i])
    backtracking(candidates, target - candidates[i], i, solution, results);
    solution.pop();
  }
}

52. N皇后 II

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
  const results = [];

  const board = Array.from({ length: n }).map(() => Array.from({ length: n }));
  backtracking(0,  board, [], results);

  return results.length;
};

function backtracking(row, board, solution, results) {
  const n = board.length;

  if (row === board.length) {
    console.log('solution:', [...solution]);
    results.push([...solution]);
    return;
  }

  for (let col = 0; col < n; col++) {
    solution.push(row + ',' + col);
    board[row][col] = 'Q';

    if (check(row, col, board)) {
      backtracking(row + 1, board, solution, results);
    }

    board[row][col] = '.';
    solution.pop();
  }
}

// check 函数还可以优化，从 O(n^2) 到 O(n)
function check(row, col, board) {
  const n = board.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === row && j === col) {
        continue;
      }
      if (board[i][j] === 'Q' && 
        (
          i === row ||               // 同行
          col === j ||               // 同咧
          i + j === row + col ||     // 左斜对角线 
          i - j === row - col        // 右斜对角线 
        )
      ) {
        return false;
      }
    }
  }

  return true;
}