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

大家好，我是柒八九。

今天，我们继续探索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的字符串

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版

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