• Leetcode hot 100之回溯O(N!)：选择/DFS

    目录

    框架：排列/组合/子集

    元素无重不可复选

    全排列

    子集

    组合：[1, n] 中的 k 个数

    分割成回文串

    元素无重不可复选：排序，多条值相同的只遍历第一条

    子集/组合

    先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过 

    排列

    元素无重可复选

    子集/组合：sum=target

    排列：去除 used 剪枝

    N皇后

    如果不能成功，那么返回的时候我们就还要把这个位置还原。这就是回溯算法，也是试探算法。

    解决一个回溯问题，实际上就是一个决策树的遍历过程。

    1、路径：已选择。

    2、选择列表：可选择。

    3、结束条件：无选择。

    框架：排列/组合/子集

    1. result = []
    2. function backtrack(路径, 选择列表):
    3.     if 满足结束条件:
    4.         result.add(路径)
    5.         result.push([...path])或者result.push(path.slice())//path还会改变，所以不能传引用地址
    6.         return
    7.  
    8.     for 选择 in 选择列表:
    9.         做选择push
    10.         backtrack(路径, 选择列表)
    11.         撤销选择pop
    12.  
    13. 数组（有一定的剪枝，不用判断是否use）
    14. const backtrack = (start) => {
    15.         
    16.         // 回溯算法标准框架
    17.         for (let i = start; i < nums.length; i++) {
    18.             // 做选择
    19.             track.push(nums[i]);
    20.             // 回溯遍历下一层节点
    21.             backtrack(i + 1);
    22.             // 撤销选择
    23.             track.pop();
    24.         }
    25.     };
    26.     
    27.     backtrack(0);
    28. 图
    29. function backtrack(nums, used, track, res) {
    30.     for (let i = 0; i < nums.length; i++) {
    31.         if (used[i]) {
    32.             continue;
    33.         }
    34.         track.push(nums[i]);
    35.         used[i] = true;
    36.         backtrack(nums, used, track, res);
    37.         track.pop();
    38.         used[i] = false;
    39.     }
    40. }
    41.  
    42. 全排列中
    43. 做选择/撤销选择 可用if(path.includes(item)) continue;代替

    元素无重不可复选

    全排列

    key：

    1. path.length == string.length
    2. path.includes(item)
    1. const _permute = string => {
    2.     const res = [];
    3.  
    4.     const backtrace = path => {
    5.         if(path.length == string.length){
    6.             res.push(path);
    7.             return;
    8.         }
    9.         for(const item of string) {
    10.             if(path.includes(item)) continue;
    11.             backtrace(path + item);
    12.         }
    13.     };
    14.  
    15.     backtrace('');
    16.     return res;
    17. }

    子集

    输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集

    比如输入 nums = [1,2,3]，算法应该返回如下子集：

    [ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]


    1. /**
    2.  * @param {number[]} nums
    3.  * @return {number[][]}
    4.  */
    5. var subsets = function(nums) {
    6.     // 用于存储结果
    7.     const res = [];
    8.     // 用于记录回溯路径
    9.     const track = [];
    10.     
    11.     /**
    12.      * 回溯算法的核心函数，用于遍历子集问题的回溯树
    13.      * @param {number} start - 控制树枝的遍历，避免产生重复子集
    14.      */
    15.     const backtrack = (start) => {
    16.         // 前序遍历位置，每个节点的值都是一个子集
    17.         res.push([...track]);
    18.         
    19.         // 回溯算法标准框架
    20.         for (let i = start; i < nums.length; i++) {
    21.             // 做选择
    22.             track.push(nums[i]);
    23.             // 回溯遍历下一层节点
    24.             backtrack(i + 1);
    25.             // 撤销选择
    26.             track.pop();
    27.         }
    28.     };
    29.     
    30.     backtrack(0);
    31.     return res;
    32. };

    组合：[1, n] 中的 k 个数

    返回范围 [1, n] 中所有可能的 k 个数的组合，剪枝

    1. let result = []
    2. let path = []
    3. var combine = function(n, k) {
    4.   result = []
    5.   combineHelper(n, k, 1)
    6.   return result
    7. };
    8. const combineHelper = (n, k, startIndex) => {
    9.   if (path.length === k) {
    10.     result.push([...path])
    11.     return
    12.   }
    13.   for (let i = startIndex; i <= n - (k - path.length) + 1; ++i) {
    14.     path.push(i)
    15.     combineHelper(n, k, i + 1)
    16.     path.pop()
    17.   }
    18. }

    分割成回文串

    • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。
    • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。

    1. /**
    2.  * @param {string} s
    3.  * @return {string[][]}
    4.  */
    5. const isPalindrome = (s, l, r) => {
    6.     for (let i = l, j = r; i < j; i++, j--) {
    7.         if(s[i] !== s[j]) return false;
    8.     }
    9.     return true;
    10. }
    11.  
    12. var partition = function(s) {
    13.     const res = [], path = [], len = s.length;
    14.     backtracking(0);
    15.     return res;
    16.     function backtracking(startIndex) {
    17.         if(startIndex >= len) {
    18.             res.push(Array.from(path));
    19.             return;
    20.         }
    21.         for(let i = startIndex; i < len; i++) {
    22.             if(!isPalindrome(s, startIndex, i)) continue;
    23.             path.push(s.slice(startIndex, i + 1));
    24.             backtracking(i + 1);
    25.             path.pop();
    26.         }
    27.     }
    28. };

    元素无重不可复选：排序，多条值相同的只遍历第一条

    子集/组合

    nums = [1,2,2]，你应该输出：

    [ [],[1],[2],[1,2],[2,2],[1,2,2] ]

    如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：

    先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过 

    排列

    1. // 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
    2. // 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
    3.  
    4. /**
    5.  * @param {number[]} nums
    6.  * @return {number[][]}
    7.  */
    8.  var permuteUnique = function(nums) {
    9.     let res = [];
    10.     let track = [];
    11.     let used = new Array(nums.length).fill(false);
    12.  
    13.     // 先排序，让相同的元素靠在一起
    14.     nums.sort((a, b) => a - b);
    15.     backtrack(nums, used, track, res);
    16.  
    17.     return res;
    18. };
    19.  
    20. /**
    21.  * @param {number[]} nums
    22.  * @param {boolean[]} used
    23.  * @param {number[]} track
    24.  * @param {number[][]} res
    25.  */
    26. function backtrack(nums, used, track, res) {
    27.     if (track.length === nums.length) {
    28.         res.push(track.slice());
    29.         return;
    30.     }
    31.  
    32.     for (let i = 0; i < nums.length; i++) {
    33.         if (used[i]) {
    34.             continue;
    35.         }
    36.         // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
    37.         if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
    38.             continue;
    39.         }
    40.         track.push(nums[i]);
    41.         used[i] = true;
    42.         backtrack(nums, used, track, res);
    43.         track.pop();
    44.         used[i] = false;
    45.     }
    46. }

    元素无重可复选

    子集/组合：sum=target

    想让每个元素被重复使用，我只要把 i + 1 改成 i 即可

    给之前的回溯树添加了一条树枝，在遍历这棵树的过程中，一个元素可以被无限次使用

    这棵回溯树会永远生长下去，所以我们的递归函数需要设置合适的 base case 以结束算法，即路径和大于 target 时就没必要再遍历下去了 

    排列：去除 used 剪枝

    N皇后

    在 n * n 的棋盘上要摆 n 个皇后，
    要求：任何两个皇后不同行，不同列也不在同一条斜线上，
    求给一个整数 n ，返回 n 皇后的摆法数。

    要求：空间复杂度 O(1) ，时间复杂度O(n!)

    1. 要确定皇后的位置，其实就是确定列的位置，因为行已经固定了
    2. 进一步讲，也就是如何摆放 数组arr [0,1,2,3,...,n-1]
    3. 如果没有【不在同一条斜线上】要求，这题其实只是单纯的全排列问题
    4. 在全排列的基础上，根据N皇后的问题，去除一些结果

    • arr ：n个皇后的列位置

    • res ：n皇后排列结果

    • ruler： 记录对应的列位置是否已经占用（也是是否有皇后），如果有，那么设为1，没有设为0

    • setPos ：哈希集合，标记正斜线（从左上到右下）位置，如果在相同正斜线上，坐标(x,y)满足 y-x 都相同，(y1 - x1)应该等于(y2 - x2)。

    • setCon ：哈希集合，标记反正斜线（从y右上到左下）位置，如果在相同反斜线上，坐标(x,y)满足 x+y 都相同，(x1 + y1)应该等于(x2 + y2)。

    • 是否在同一斜线上，其实就是这两个点的所形成的斜线的斜率是否为±1。点P(a,b) ，点Q(c,d)

      （1）斜率为1 (d-b)/(c-a) = 1，横纵坐标之差相等

      （2）斜率为-1 (d-b)/(c-a) = -1 ，等式两边恒等变形 a+b = c + d ，横纵坐标之和相等

    1. /**
    2.  *
    3.  * @param n int整型 the n
    4.  * @return int整型
    5.  */
    6. function Nqueen(n) {
    7.     let res = []; //二维数组，存放每行Q的列坐标
    8.     let isQ = new Array(n).fill(0); //记录该列是否有Q
    9.     let setPos = new Set(); //标记正对角线
    10.     let setCon = new Set(); // 标记反对角线
    11.     //给当前row找一个col
    12.     const backTrace = (row, path) => {
    13.         if (path.length === n) {
    14.             res.push(path);
    15.             return;
    16.         }
    17.         for (let col = 0; col < n; col++) {
    18.             if (
    19.                 isQ[col] == 0 &&
    20.                 !setPos.has(row - col) &&
    21.                 !setCon.has(row + col)
    22.             ) {
    23.                 path.push(col);
    24.                 isQ[col] = 1;
    25.                 setPos.add(row - col);
    26.                 setCon.add(row + col);
    27.                 backTrace(row + 1, path);
    28.                 path.pop();
    29.                 isQ[col] = 0;
    30.                 setPos.delete(row - col);
    31.                 setCon.delete(row + col);
    32.             }
    33.         }
    34.     };
    35.     backTrace(0, []);
    36.     return res.length;
    37. }
    38. module.exports = {
    39.     Nqueen: Nqueen,
    40. };

    动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。

    二维

    单词搜索

    1. var exist = function(board, word) {
    2.     const h = board.length, w = board[0].length;
    3.     const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    4.     const visited = new Array(h);
    5.     for (let i = 0; i < visited.length; ++i) {
    6.         visited[i] = new Array(w).fill(false);
    7.     }
    8.     const check = (i, j, s, k) => {
    9.         if (board[i][j] != s.charAt(k)) {
    10.             return false;
    11.         } else if (k == s.length - 1) {
    12.             return true;
    13.         }
    14.         visited[i][j] = true;
    15.         let result = false;
    16.         for (const [dx, dy] of directions) {
    17.             let newi = i + dx, newj = j + dy;
    18.             if (newi >= 0 && newi < h && newj >= 0 && newj < w) {
    19.                 if (!visited[newi][newj]) {
    20.                     const flag = check(newi, newj, s, k + 1);
    21.                     if (flag) {
    22.                         result = true;
    23.                         break;
    24.                     }
    25.                 }
    26.             }
    27.         }
    28.         visited[i][j] = false;
    29.         return result;
    30.     }
    31.  
    32.     for (let i = 0; i < h; i++) {
    33.         for (let j = 0; j < w; j++) {
    34.             const flag = check(i, j, word, 0);
    35.             if (flag) {
    36.                 return true;
    37.             }
    38.         }
    39.     }
    40.     return false;
    41. };

  • 相关阅读:
    Unity --- 给物体添加重力
    JavaScript学习（五）——首页跳转实现
    【部署】Linux Shell脚本部署java程序 （jar包）
    FX110网：香港交易所宣布开发Orion衍生品平台，预计于 2028 年推出
    使用springboot实现jsonp|jsonp的实现|JSONP的实现使用springboot
    ObjectARX简单自定义实体的实现
    MySQL到底大小写敏感还是不敏感?
    工业智能网关在能耗“双控”的智能化应用
    js模块化
    基于Python的二次元头像生成器 课程报告+源码
  • 原文地址：https://blog.csdn.net/qq_28838891/article/details/133667638