递归-回溯算法模板

[evenMai92]

参考一
参考二
参考三
「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 棋盘问题：N皇后，解数独等等

回溯法的模板：

backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

子集问题

子集问题（一）


「本题其实可以不需要加终止条件」，因为start >= nums.length，本层for循环本来也结束了，本来我们就要遍历整颗树。

并不会无限递归，因为每次递归的下一层就是从i+1开始的。

如果要写终止条件，注意：result.push(nums[i]);要放在终止条件的上面，如下：

const res = []; // 结果
function subsets(nums) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums, temp);

  return res;
}

function backtracking(start, nums, temp) {
  res.push([...temp]);; // 收集子集，要放在终止添加的上面，否则会漏掉结果
  if (start>= nums.length) { // 终止条件可以不加
      return;
  }

  // 从start开始遍历，避免重复
  for(let i = start; i < nums.length; i++) {
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i + 1, nums, temp);
    // 回溯
    temp.pop();
  }
}
subsets([1,2,3])

子集问题（二）


这个题目与前面的子集题目相比较，差别就在于包含重复的子集，也就是不能顺序改变而已，元素一样的子集出现。

这个题目框架还是不变的，但是，要做一下简单的剪枝操作：怎么排除掉重复的子集。

这里我通过Map数据结构来去重，如下：

const res = []; // 结果
const map = new Map(); // 用来判断是否重复
function subsets(nums) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums, temp);

  return res;
}

function backtracking(start, nums, temp) {
  // 去重
  if(!map.has(temp.join())) {
    res.push([...temp]);; // 收集子集，要放在终止添加的上面，否则会漏掉结果
    map.set(temp.join(), temp);
  }
  // 从start开始遍历，避免重复
  for(let i = start; i < nums.length; i++) {
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i + 1, nums, temp);
    // 回溯
    temp.pop();
  }
}
subsets([1,1,2])

全排列问题

全排列问题（一）

排列是有序的，也就是说[1,2] 和[2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。

可以看出元素1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用start了，而且我们这边还要进行剪枝（temp集合中有的就排除）。如下：

const res = []; // 结果
function subsets(nums) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums, temp);

  return res;
}

function backtracking(start, nums, temp) {
 // 终止条件
  if(nums.length === temp.length) {
    res.push([...temp]);
    return;
  }

  // 从0开始遍历
  for(let i = 0; i < nums.length; i++) {
    // 去重
    if(temp.includes(nums[i])) {
      continue;
    }
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i + 1, nums, temp);
    // 回溯
    temp.pop();
  }
}
subsets([1,2,3])

组合问题

组合问题（一）


可以直观的看出其搜索的过程：「for循环横向遍历，递归纵向遍历，回溯不断调整结果集」

其中优化回溯算法只有剪枝一种方法，在回溯算法：组合问题再剪剪枝中把回溯法代码做了剪枝优化，树形结构如图：

「回溯算法：求组合问题！剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了」。

「在for循环上做剪枝操作是回溯法剪枝的常见套路！」，如下。

const res = []; // 结果
function subsets(nums, k) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums, k, temp);

  return res;
}

function backtracking(start, nums, k, temp) {
  if(k === temp.length) {
    res.push([...temp]);
    return;
  }

  // 从start开始遍历,无优化版 i < nums.length
  // 剪枝优化 i < (nums.length - (k - temp.length) + 1)
  for(let i = start; i < (nums.length - (k - temp.length) + 1); i++) {
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i + 1, nums, k, temp);
    // 回溯
    temp.pop();
  }
}
subsets([1,2,3,4], 2);

组合总和（一）

这个题目跟之前的没有什么太大的区别，只是需要注意一个点：每个数字可以被无限制重复被选取，我们要做的就是在递归的时候，i的下标不是从i+1开始，而是从i开始。

const res = []; // 结果
function subsets(nums, target) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums, target, temp);

  return res;
}

function backtracking(start, nums, target, temp) {
  // 终止条件
  if(target < 0) {
    return;
  }
  // 获取结果
  if(target === 0) {
    res.push([...temp]);
  }

  // 从start开始遍历
  for(let i = start; i < nums.length; i++) {
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i, nums, target - nums[i], temp);
    // 回溯
    temp.pop();
  }
}
subsets([2,3,6,7], 7);

组合总和（二）

题目差不多，只不过这里只是每个数字只能用一次，同时也是不能包含重复的组合，所以，用之前Map去重方法解决.

const res = []; // 结果
const map = new Map();
function subsets(nums, target) {
  if(nums.length === 0) return null;
  const temp = []; // 缓存结果值
  backtracking(0, nums.sort(), target, temp);

  return res;
}

function backtracking(start, nums, target, temp) {
  // 终止条件
  if(target < 0) {
    return;
  }
  // 获取结果（判断是否重复）
  if(target === 0 && !map.has(temp.join())) {
    res.push([...temp]);
    map.set(temp.join(), temp);
  }

  // 从start开始遍历
  for(let i = start; i < nums.length; i++) {
    // 处理节点;
    temp.push(nums[i]);
    // 递归
    backtracking(i + 1, nums, target - nums[i], temp);
    // 回溯
    temp.pop();
  }
}
subsets([10,1,2,7,6,1,5], 8);