「🦆TSK的博客」

Appearance

On this page

回溯算法 ​

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。

回溯是递归的副产品，只要有递归就会有回溯

回溯法解决的问题 ​

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

🔥🔥🔥

组合是不强调元素顺序的，排列是强调元素顺序。

INFO

回溯法解决的问题都可以抽象为树形结构

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度

组合 ​

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
图中可以发现 n 相当于树的宽度，k 相当于树的深度
图中每次搜索到了叶子节点，我们就找到了一个结果。

剪枝优化 ​

如果 for 循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

txt
for (int i = startIndex; i <= n; i++) {

  1. 已经选择的元素个数：path.size();

  2. 还需要的元素个数为: k - path.size();

  3. 在集合 n 中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

为什么有个+1 呢，因为包括起始位置，我们要是一个左闭的集合。

举个例子，n = 4，k = 3， 目前已经选取的元素为 0（path.size 为 0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。所以优化之后的 for 循环是

txt
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
js
function backtrace(num,k){
  let t = [],r = [];
    function combineHelper (i){
      if(t.length == k){
        //  t 只有一份，根据 递归 进行不断修改
        r.push([...t])
        return
      }
      //剪枝
      for(;i<num - k - t.length + 1){ 
      // 未减枝
      for(;i<=num;i++){ 
        t.push(i);
        combineHelper (i+1)
        t.pop()
      }
    }
    combineHelper (1)
  return r
}
let r = backtrace(num,k)

组合总和III ​

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

所有数字都是正整数。 解集不能包含重复的组合。

  • 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
  • 示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
js
let k = 2,n = 4;

function backtrace(n, k) {
  let t = [],r = [],total = 0;

  function combineHelper(startIndex) {
    if(total>n)return;

    if (t.length == k) {
      if (total == n) {
        r.push([...t]);
      }
    }
    // 限定在 9 - total 里面
    for (; startIndex <= 9 - total; startIndex++) {
      t.push(startIndex);
      total += startIndex;
      combineHelper(startIndex + 1);
      total -= t.pop();
    }
  }
  combineHelper(1);
  return r;
}
let r = backtrace(n,k)

组合总和 ​

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。

  1. 示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
  2. 示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5]

核心问题在于无限制重复选取,解集中不能有重复的组合,
所以由于是无限制重复选取，开始位置使用 i，而不是 i+1

js
function backtrace(nums, target) {
  let t = [],
    r = [],
    total = 0;
  function combineHelper(startIndex) {
    if (total == target) {
      r.push([...t]);
      return;
    }

    for (let i = startIndex; i < nums.length; i++) { 
      if(nums[i] > target - total) break;
      t.push(nums[i]);
      total += nums[i];
      combineHelper(i); 
      total -= t.pop();
    }
  }
  combineHelper(0);
  return r;
}
let r = backtrace(nums, target);

组合总和II ​

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。

  1. 输入: candidates = [10,1,2,7,6,1,5], target = 8; 输出: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

🔥🔥🔥

used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
used[i - 1] == false，说明同一树层candidates[i - 1]使用过

因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上

js
let nums = [10,1,2,7,6,1,5], target = 8;

function backtrace(nums){
  // 先要排序
  nums = nums.sort((a,b)=>a-b)

  let r = [],t = [],total = 0,used = new Array(nums.length).fill(false);
  function helper(startIndex){
    if(total == target){
      r.push([...t])
      return
    }

    for(let i = startIndex;i<nums.length;i++){
      // 如果不加 !used[i-1],会失去 [1,1,6]
      if(!used[i-1] && i > 0 && nums[i] == nums[i-1] ) continue;

      used[i] = true
      total+=nums[i]
      t.push(nums[i]);
      helper(i+1)
      total-= t.pop()
      used[i] = false
    }
  }
  helper(0)
  return r
}
let r =  backtrace(nums,target)

子集 ​

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

js
var subsets = function(nums) {
    let result = []
    let path = []
    function backtracking(startIndex) {
        result.push([...path])
        for(let i = startIndex; i < nums.length; i++) {
            path.push(nums[i])
            backtracking(i + 1)
            path.pop()
        }
    }
    backtracking(0)
    return result
}

子集II ​

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）

解集不能包含重复的子集
输入:[1,2,2]，输出: [ [2], [1], [1,2,2], [2,2], [1,2], [ ] ]

使用 used 数组记录使用过的元素,也可以使用i > startIndex && nums[i] == nums[i-1] 简单的判断

js
let nums = [1,2,2];

function backtrace(nums){
  nums = nums.sort((a,b)=>a-b)
  let r = [],t = [],used = new Array(nums.length).fill(false);

  function helper(startIndex){
    r.push([...t])
    for(let i = startIndex;i<nums.length;i++){
        // if(!used[i-1] && i > 0 && nums[i] == nums[i-1] ) continue;
        if(i > startIndex && nums[i] == nums[i-1] ) continue;
        used[i] = true
        t.push(nums[i]);
        helper(i+1)
        t.pop()
        used[i] = false
    }
  }
  
  helper(0)
  return r
}

递增子序列 ​

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
输入: [4, 6, 7, 7],输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

在图中可以看出，同一父节点下的同层上使用过的元素就不能再使用了

js
let nums = [4, 6, 7, 7];

function backtrace(nums){
  let r = [],t = [];
  
  function helper(startIndex){
    if(t.length>=2){
        r.push([...t])
    }

    // 只记录本层元素是否重复使用，新的一层会被重新定义(清空)
    let userd = []
    for(let i = startIndex;i<nums.length;i++){
      if((t.length>0 && nums[i] < t[t.length - 1]) || userd[nums[i]]){
          continue;
        }   
        userd[nums[i]] = true
        t.push(nums[i]);
        helper(i+1)
        t.pop()
      }
  }
  
  helper(0)
  return r
}
let r =  backtrace(nums)

全排列 ​

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

输入: [1,2,3]，输出：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

INFO

这个不能设置起始索引,因为有 [3,1,2]这种
同时要求不能有重复,所以使用 userd 进行收集 同一个树枝上的重复项

从图中可以看出，在同一树枝中不需要收集已经用过的

js
let nums = [1,2,3];

function backtrace(nums){
  let r = [],t = [],userd = new Array(nums.length).fill(false);

    function helper(){
      if(t.length==nums.length){
        r.push([...t])
        return
      }

      for(let i = 0;i<nums.length;i++){
        // 删除当前树枝中已经用过的
        if(userd[i])continue 
        userd[i] = true
        t.push(nums[i]);
        helper()
        t.pop()
        userd[i] = false
      }
  }
  
  helper(0)
  return r
}

全排列 II ​

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

  1. 输入:nums = [1,1,2]，输出：[[1,1,2], [1,2,1], [2,1,1]]
  2. 输入:nums = [1,2,3]，输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

这道题目和全排列的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全排列。

强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

js
let nums = [1, 1, 2];

function backtrace(nums) {
  let r = [],
    t = [],
    used = new Array(nums.length).fill(false);

  function helper() {
    if (t.length == nums.length) {
      r.push([...t]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      // 同一树层下不能取相同的
      if (i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;
      // 因为是可以重复选取,所以要把自己给排除掉
      if(used[i]) continue
    
        used[i] = true;
        t.push(nums[i]);
        helper();
        t.pop();
        used[i] = false;
      
    }
  }

  helper(0);
  return r;
}
let r = backtrace(nums);

回溯总结 ​

深刻理解下面的这张图

Updated at: