❝ 弱小和无知不是生存的障碍，傲慢才是 --《三体·死神永生》
❞

大家好，我是「柒八九」。

今天，我们继续探索JS算法相关的知识点。我们来谈谈关于「回溯法」的相关知识点和具体的算法。

如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。

文章list

1. 整数
2. 常规排序算法
3. 数组
4. 字符串
5. 链表
6. 栈
7. 队列
8. 二叉树

好了，天不早了，干点正事哇。

你能所学到的知识点

❝

1. 何为回溯法
2. 集合的组合、排列
3. 利用回溯算法解决其他问题

❞

何为回溯法

❝ 回溯法可以看做「暴力法的升级版」,它在解决问题时的每一步都「尝试所有可能的选项」，最终「找出所有可行的解决方案」。
❞

回溯法非常适合解决「由多个步骤组成的问题，并且每个步骤都有多个选项」。

❝ 用回溯法解决问题的过程可以形象的「用一个树形结构表示，求解问题的每个步骤可以看作树中的一个节点」。如果在某一步有n个可能的「选项」，那「每个选项是树中的一条边」，经过这些边就可以到达该节点的n个子节点。
❞

在采用回溯法解决问题时，

• 如果到达树形结构的「叶节点」，就找到了「问题的一个解」。
• 如果希望找到更多的解，可以「回溯到当前节点的父节点」，再尝试父节点「其他」的选项
• 如果父节点所有可能的选项都已经试过，那么再回溯到父节点的父节点，继续尝试其他选项，这样「逐层回溯到树的根节点」。

❝ 因此，采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行「深度优先遍历」
❞

通常，回溯法的深度优先遍历用「递归」代码实现。

如果在前往某个节点时对问题的解的「状态进行了修改」，那么在回溯到它的父节点时，要「清除相应的修改」。

剪枝

由于回溯法是在所有选项形成的树上进行深度优先遍历，如果解决问题的步骤较多或每个步骤都面临多个选项，那么遍历整颗树将需要较多的时间。如果明确知道某些子树没有必要遍历，那么在遍历的时候应该避开这些子树以优化效率。 通常将使用回溯法时避免遍历不必要的子树的方法称为「剪枝」。

集合的组合、排列

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）形成一个子集Subset。一个子集又称为一个组合。如果两个子集（组合）的元素完全相同只是顺序不同，那么它们可以看作同一个子集（组合）。

从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）并按照某种顺序形成一个「排列」。 m等于n的排列有称为「全排列」。如果两个排列的元素完全相同只是顺序不同，那么它们就是两个不同的排列。 「排列与元素的顺序相关」。

所有子集

题目描述：

❝ 输入一个「不含重复数字」的数据集合，请找出它的「所有」子集

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
❞

分析

1. 子集就是从一个集合中「选出若干元素」。
   • 「如果集合中包含n个元素，那么生成子集可以分为n步」
2. 每一步从集合中取出一个数字，此时「面临两个选择」
   1. 将该数字添加到子集中
   2. 不将该数字添加到子集中
3. 生成一个子集可以「分成若干步，并且每一步都面临若干选择」 -- 「回溯法」

代码实现

function subsets(nums){
  let result = [];
  if(nums.length == 0) return result;
  
  (function helper(nums,index,subset,result){
    if(index === nums.length){ // 基线条件
      result.push([...subset])
    }else if(index < nums.length){
      helper(nums,index + 1, subset,result); // 不将数字添加到子集
      
      subset.push(nums[index]); // 将数字添加到子集中
      helper(nums,index + 1,subset,result);
      subset.pop();
    }
  })(nums,0,[],result)
  return result;
}

代码解释

1. 递归函数helper有四个参数
   1. nums 是数组nums,包含输入集合的所有数字。可以逐一从集合中「取出一个数字并选择是否将数字添加到子集中」。
   2. index是当前取出的数字在数组nums中下标
   3. subset是「当前子集」
   4. result是「所有已经生成」的子集
2. 每当从数组nums中取出一个下标为index的数字时，都要考虑是否将该数字添加到子集subset中。
   1. 「不将数字添加到子集的情形」。不对子集进行任何操作，只需要「调用递归函数helper处理数组nums中的下一个数字(下标增加1)」
      • helper(nums,index + 1,subset,result)
   2. 「将下标为index的数字添加到子集subset中」。
      • 在将该数字添加到子集之后
        • subset.push(nums[index])
      • 接下来调用递归函数处理数组nums下一个数字(下标增加1)
        • helper(nums,index + 1, subset, result)
      • 「等递归函数执行完成之后，函数helper也执行完成，接下来将回溯到前一个数字的函数调用处继续执行。」
        • 在回溯到父节点之前，应该「清除」已经对子集状态进行的修改。
        • subset.pop()
3. 「当index等于数组nums的长度时候」，表示数组中的所有数字都已经处理过，因此可以生成一个子集。将子集subset添加到result中
   • 在此处加入的是subset的副本，因为接下来还需要修改subset用以获得其他的子集
   • result.push([...subset])

包含k个元素的组合

题目描述：

❝ 输入n和k，请输入从1到n中选取k个数字组成的所有「组合」。

输入：n = 3, k = 2
输出：[[1,2],[1,3],[2,3]]
❞

分析

1. 集合的组合也是一个子集，求集合的组合的过程和求子集的过程是一样的。
2. 此题增加了一个限制条件，只找包含k个数字的组合
3. 在上一个题目「所有子集」增加一些限定条件，就可以处理该题。

代码实现

function combine(n,k){
 let result = [];
 (function helper(n,k,index,subset,result){
   if(subset.length === k){ // 基线条件
     result.push([...subset])
   }else if(index <= n){
     helper(n,k, index + 1, subset,result); // 不将数字添加到子集
     
     subset.push(index); // 将数字添加到子集中
     helper(n,k,index + 1,subset,result); 
     subset.pop();
   }
 })(n,k,1,[],result)
 return result;
}

代码解释

1. 递归函数helper有五个参数
   1. n 是数组范围1~n
   2. k是组合的长度
   3. index是当前取出的数字
   4. subset是当前子集
   5. result是所有「已经生成」的子集
2. 当subset.length等于k时，进行子集的收集处理
   • result.push([...subset])
3. 还有一点 index是从1开始的。

允许重复选择元素的组合

题目描述：

❝ 给定一个「没有重复数字」的正整数集合，请找出所有元素之和等于某个给定值(target)的所有组合。
同一个数字可以在组合中「重复任意次」。

输入：candidates = [2,3,6,7], target = 7
输出：[[7],[2,2,3]]
❞

分析

1. 关于组合的相关题目，使用「回溯法」解决
2. 用回溯法解决的问题都能够「分成若干步来解决，每一步都面临着若干选择」
3. 对于从集合中选取数字组成组合的问题而言，集合中有多少个数字，解决这个问题就需要多少步。
4. 每一步从集合中取出一个下标为i的数字,此时，「面临两个选择」。
   1. 「什么都不做」 --选择「跳过这个数字」不将该数字添加到组合中，接下来处理下标为i + 1的数字。
   2. 「将数字添加到组合中」 -- 由于一个数字可以重复在组合中「重复出现」，也就是下一步「可能再次选择同一个数字」，因此下一步仍然处理下标为i的数字。

代码实现

function combinationSum(nums,target){
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target ==0){ //基线条件
      result.push([...subset])
    }else if(target > 0 && index < nums.length){
      helper(nums,target,index + 1,subset,result); // 不将数字添加到子集
      
      subset.push(nums[index]); // 将数字添加到子集中
      helper(nums,target - nums[index],index,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

代码解释

1. 由于nums[index]可能在组合中「重复出现」，因此在index处，「选择了将数字添加到组合」的选择，「递归调用helper时，index是不需要+1的」。
2. 每当选择了一个数据后，需要更新target
   • target - nums[index]
3. 当某次遍历的时候，target为0时，说明现在「子集」已经满足情况。
   • result.push([...subset])
4. 由于题干中，数据都是「正整数」，在操作过程中，target只能少，不能多，所以可以判断target与0的关系，来进行「剪枝」处理。
   • if(target>0 && index < nums.length)

举一反三

上面的几个题目都是关于数学上的组合、集合，其实这些「模型」可以应用到很多其他问题中。

例如，当客人走近餐厅准备吃饭，一种点菜的方法就是生成一个符合条件的组合。

• 如果每道菜「只点一份」，那么就是找出「所有」符合条件的组合
• 如果总共「只能点k道菜」，那么就是找出「包含k个元素」的所有符合条件的组合
• 如果每道菜可以「点任意多份」，那么就是找出「允许选择重复元素」的符合条件的组合

包含重复元素集合的组合

题目描述：

❝ 给定一个可能「包含重复数字」的整数集合，请找出所有元素之和等于某个给定值（target）的所有组合。
输出中不得包含重复的组合。

输入：candidates = [2,5,2,1,2], target = 5
输出：[[1,2,2],[5]]
❞

分析

1. 如果输入的集合中有重复的数字，不经过特殊处理将产生重复的组合。
2. 避免重复的组合的方法是「当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字。」
3. 为了方便跳过后面所有值相同的数字，可以「将集合中的所有数字排序，把相同的数字放在一起」，这样方便比较数字。
   • 当决定「跳过某个值」时，可以按顺序扫描后面的数字，「直到找到不同的值为止」。

代码实现

function combinationSum(nums,target){
  nums.sort((a,b) => a -b);
  
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target == 0){ // 基线条件
      result.push([...subset]);
    }else if(target > 0 && index < nums.length){
      // 选择跳过某批值相同的数字
      helper(nums,target,getNext(nums,index),subset,result); 
      
      subset.push(nums[index]);
      helper(nums,target - nums[index], index + 1,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

辅助函数

function getNext(nums,index){
  let next = index;
  while(next < nums.length && nums[next] == nums[index]){
    next++;
  }
  return next;
}

代码解释

1. 排序是为了方便跳过相同的数字。
   • 这个处理方式和在数组中处理「三数之和」的道理是一样的
2. 利用getNext找到与当前index值不同的下标

没有重复元素集合的全排列

题目描述：

❝ 给定一个「没有重复数字」的集合，请找出它的所有全排列。

输入：nums = [0,1]
输出：[[0,1],[1,0]]
❞

分析

1. 排列和组合(子集)不同，排列「与元素的顺序相关」，交互数字能够得到不同的排列。
2. 生成全排列的过程，就是「交换输入集合中元素的顺序以得到不同的排列」。
3. 如果输入的集合有n个元素，
   • 那么生成一个全排列需要n步
   • 当生成排列的第一个数字时，面临着n个选项
   • 当生成排列的第二个数字时，面临着n-1个选项
4. 解决「问题可以分成n步，每一步面临着若干选项」 -- 「回溯法」

代码实现

function permute(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index == nums.length){
      result.push([...nums]) // 基线条件
    }else {
      for(let j = index;j<nums.length;j++){
        swap(nums,index,j); // 数字替换位置
        helper(nums,index + 1,result);
        swap(nums,index,j); // 清除对排列状态的修改
      }
    }
  })(nums,0,result)
  return result;
}

辅助函数

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代码解释

1. 在函数执行过程「总数组nums保存着当前排列的状态」
2. 当函数helper生成排列的下标为index的数字时，
   • 下标从0到index-1的数字都「已经选定」，
   • 但数组nums中下标从index到n-1的数字(假设数组的长度为n)都有可能放到排列的下标为index的位置
   • 因此函数helper中「有一个for循环逐一用下标为index的数字交互它后面的数字」。
   • for循环包含下标为index的数字本身，因为它自己也能放在排列下标为index的位置
   • swap(nums,index,j)
3. 交互之后接着调用递归函数生成排列中下标为index + 1的数字
   • helper(nums,index + 1, result)
4. 在函数退出之前需要「清除对排列状态的修改」
   • swap(nums,index,j)

包含重复元素集合的全排列

题目描述：

❝ 给定一个包含「重复数据」的集合，请找出它的所有全排列

输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
❞

分析

1. 如果集合中有重复的数字，那么「交换集合中重复的数字得到的全排列是同一个全排列」
2. 当处理到全排列的第i个数字时，如果已经将某个值为m的数字交换为排列的第i个数字，那么再遇到其他值为m的数字就「跳过」

代码实现

function permuteUnique(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index === nums.length){
      result.push([...nums]); // 基线条件
    }else {
      let map = {};
      for(let j = index;j<nums.length;j++){
        if(!map[nums[j]]){
          map[nums[j]] = true;
          
          swap(nums,index,j);
          helper(nums,index + 1,result);
          swap(nums,index,j);
        }
      }
    }
  })(nums,0,result)
  return result;
}

辅助函数

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代码解释

1. 用一个「对象map，来保存已经交换到排列下标为index的位置的所有值」。
2. 只有当一个数值之前没有被交换到第index位时才做交换，否则直接跳过
   • 在for循环中多一层判断
   • if(!map[nums[j]])

解决其他问题

除了可以解决与集合排列、组合相关的问题，回溯法还能解决很多问题。

如果解决一个问题需要「若干步骤」，并且每一步都面临「若干选择」，当在「某一步」做了某个选择之后，前往下一步仍然面临若干选项。那么可以考虑用「回溯法」

❝ 通常，回溯法可以用「递归代码」实现。
❞

生成匹配的括号

题目描述：

❝ 输入一个正整数n,请输出「所有」包含n个左括号和n个右括号的组合，要求每个组合的左括号和右括号匹配。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
❞

分析

1. 输入n，生成的括号组合包含n个左括号和n个右括号。
   • 因此，生成这样的组合需要2n步，每一步生成一个括号
   • 「每一步都面临着两个选项」，既可能生成左括号也可能生成右括号
   • 「回溯法」解决
2. 生成括号组合时，需要注意每一步都需要满足两个限制条件
   1. 左括号或右括号的数目不能超过n个
   2. 括号匹配原则： 即在「任意步骤」中已经生成的右括号的数目不能超过左括号的数目

代码实现

function generateParenthesis(n){
  let result = [];
  (function helper(left,right,subset,result){
    if(left == 0 && right ==0){
      result.push(subset); //基线条件
      return ;
    }
    // 已经生成的左括号的数目少于`n`个
    if(left > 0){ 
      helper(left -1,right,subset + "(",result)
    }
    // 已经生成的右括号的数目少于已经生成的左括号的数目
    if(left < right){ 
      helper(left,right -1,subset + ")",restule)
    }
  })(n,n,"",result)
  return result;
}

代码解释

1. 参数left:表示「还需要生成」的左括号的数目
2. 参数right：表示「还需要生成」右括号的数目。
3. 每生成一个左括号，参数left-1;每生成一个右括号，参数right -1;当left/right都等于0，一个完整的括号组合生成
   • result.push(subset);
4. 在生成一个括号时
   • 只要「已经生成的左括号的数目少于n个」(left>0)就能生成一个左括号
   • 只要「已经生成的右括号的数目少于已经生成的左括号的数目」（left < right）就能生成一个右括号

分割回文字符串

题目描述：

❝ 输入一个字符串，要求将它「分割成若干子字符串，使每个字符串都是回文」。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
❞

分析

1. 当处理到字符串中的某个字符串时候，如果包括该字符在内后面还有n个字符，那么面临n个选项
   • 分割出长度为1的字符串（只包含该字符）
   • 分割出长度为2的字符串（包含该字符及它后面的一个字符）
   • 分割出长度为x的字符串 (x<n)
   • 分割出长度为n的字符串
2. 解决这个问题需要很多步，每一步分割出一个回文字符串。

代码实现

function partition(str){
  let result = [];
  (function heler(str,start,subset,result){
    if(start == str.length){
      result.push([...subset]); // 基线条件
    }else {
      for(let i = start;i<str.length;i++){
        if(isPalinadrome(str,start,i)){
          subset.push(str.substring(start,i+1));
          helper(str,i + 1,subset,result);
          subset.pop();
        }
      }
    }
  })(str,0,[],result)
  return result;
}

辅助函数

function isPalinadrome(str,start,end){
  while(start < end){
    if(str[start++]!=str[end--]) return false;
  }
  return true
}

代码解释

1. 当处理到下标为start的字符串时，用一个for循环逐一判断从下标start开始到i结束的每个子字符串是否会回文
   • i从下标start开始，到字符串s的最后一个字符结束
2. 如果是回文，就分割出一个符合条件的子字符串，添加到subset中
   • subset.push(str.substring(start,i+1)) （substring它的第一个参数表示子字符串的开始位置，第二个位置表示结束位置--返回结果不含该位置）
   • 接着处理下标从i+1开始的剩余字符串。

小结

❝ 如果解决一个问题需要若干步骤，并且在每一步都面临着若干选项，那么可以尝试用「回溯法」解决问题。
❞

应用回溯法能够解决「集合的排列、组合」的很多问题。

❝ 回溯法都可以使用「递归」的代码实现。递归代码需要先确定「递归退出」的边界条件(基线条件)，然后逐个处理集合中的元素。
❞

对于「组合类」问题，每个数字都面临两个选项

1. 添加当前数字到组合中
2. 不添加当前数字到组合中

对于「排列类」问题，一个数字如果后面有n个数字，那么面临n+1个选择，即可以将数字和后面的数字(包括它自身)交换。

后记

「分享是一种态度」。

参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版

「全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。」