René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"回溯算法汇总一","articleBody":"上周发了篇文章，关于一名 95 后女程序员（4 年前端开发），对现状的担忧与对未来的焦虑担忧，文章一经发出，后台就收到很多反馈，大部分的人都表示认同：\r\n\r\n![WechatIMG28](https://user-images.githubusercontent.com/19721451/162015147-a5240cda-cda5-4231-819a-995c0406a57b.jpeg)\r\n\r\n\r\n因此，我决定把自己的每日进阶记录下来，有时可能 2-3 天一起，每日内容不多，如果你不清楚怎么做，就和我一起吧，如果你有规划，也可以关注「**三分钟学前端**」，添加我的微信 **pzijun_com**，将你的每日进阶记录发送到群群里，我们一起督促学习\r\n\r\n# 回溯算法\r\n\r\n**什么是回溯算法问题？**\r\n\r\n回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。它就是不断的尝试，直到拿到解。因此它类似于一种暴力穷举的算法，此类问题一般都很少考虑时间复杂度问题\r\n\r\n它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解，或得到所有满足要求的解。因此它常采用深度优先遍历（DFS）求解\r\n\r\n我们最常遇到的问题，例如：\r\n\r\n- 全排列问题\r\n- 括号生成问题\r\n- 组合总和问题\r\n- 树的深度遍历问题\r\n\r\n## 全排列问题\r\n\r\n给定一个 **没有重复** 数字的序列，返回其所有可能的全排列。\r\n\r\n```javascript\r\n输入: [1,2,3]\r\n输出:\r\n[\r\n  [1,2,3],\r\n  [1,3,2],\r\n  [2,1,3],\r\n  [2,3,1],\r\n  [3,1,2],\r\n  [3,2,1]\r\n]\r\n```\r\n\r\n它的核心思路就是类似一个多叉树的形式，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。\r\n\r\n![image.png](https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png)\r\n\r\n图片来自于：https://pic.leetcode-cn.com/0bf18f9b86a2542d1f6aa8db6cc45475fce5aa329a07ca02a9357c2ead81eec1-image.png\r\n\r\n```javascript\r\nlet permute = function(nums) {\r\n    // 使用一个数组保存所有可能的全排列\r\n    let res = []\r\n    if (nums.length === 0) {\r\n        return res\r\n    }\r\n    let used = {}, path = []\r\n    dfs(nums, nums.length, 0, path, used, res)\r\n    return res\r\n}\r\nlet dfs = function(nums, len, depth, path, used, res) {\r\n    // 所有数都填完了\r\n    if (depth === len) {\r\n        res.push([...path])\r\n        return\r\n    }\r\n    for (let i = 0; i \u003c len; i++) {\r\n        if (!used[i]) {\r\n            // 动态维护数组\r\n            path.push(nums[i])\r\n            used[i] = true\r\n            // 继续递归填下一个数\r\n            dfs(nums, len, depth + 1, path, used, res)\r\n            // 撤销操作\r\n            used[i] = false\r\n            path.pop()\r\n        }\r\n      \r\n    }\r\n}\r\n```\r\n\r\n## 括号生成问题\r\n\r\n数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。\r\n\r\n**示例：**\r\n\r\n```javascript\r\n输入：n = 3\r\n输出：[\r\n       \"((()))\",\r\n       \"(()())\",\r\n       \"(())()\",\r\n       \"()(())\",\r\n       \"()()()\"\r\n     ]\r\n```\r\n\r\n对应于本题，最开始是 `''`，我们可以每次试探增加 `(` 或 `)` ，注意：\r\n\r\n- 加入 `(` 的条件是，当前是否还有 `(` 可以选择\r\n- 加入 `)` 的时候，受到 `(` 的限制，如果已选择的结果里的 `(` 小于等于已选择里的 `)` 时，此时是不能选择 `)` 的，例如如果当前是 `()` ，继续选择 `)` 就是 `())` ，是不合法的\r\n\r\n**代码实现：**\r\n\r\n```javascript\r\nconst generateParenthesis = (n) =\u003e {\r\n    const res = []\r\n    const dfs = (path, left, right) =\u003e {\r\n        // 肯定不合法，提前结束\r\n        if (left \u003e n || left \u003c right) return\r\n        // 到达结束条件\r\n        if (left + right === 2 * n) {\r\n            res.push(path)\r\n            return\r\n        }\r\n        // 选择\r\n        dfs(path + '(', left + 1, right)\r\n        dfs(path + ')', left, right + 1)\r\n    }\r\n    dfs('', 0, 0)\r\n    return res\r\n}\r\n```\r\n\r\n## 组合总和问题\r\n\r\n给你一个 无重复元素 的整数数组 `candidates` 和一个目标整数 `target` ，找出 `candidates` 中可以使数字和为目标数 `target` 的 **所有** 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。\r\n\r\n- `candidates` 中的 同一个 数字可以无限制重复被选取 。\r\n- 如果至少一个数字的被选数量不同，则两种组合是不同的。 \r\n\r\n```javascript\r\n输入: candidates = [2,3,5], target = 8\r\n输出: [[2,2,2,2],[2,3,3],[3,5]]\r\n```\r\n\r\n对应于本题，从 `candidates` 选择数，每个数可以选择多次，使用 `index` 记录当前选到第几个数，不可向前选择，防止重复，`count` 为当前满足条件的 `index` 位的数最多可选 `count` 次，由 `0 ... count` 次往后递归\r\n- `paths`：已选数\r\n- `sum`：已选数和\r\n- `index`：当前选到第几个数\r\n\r\n```js\r\nvar combinationSum = function(candidates, target) {\r\n    let res = [], map = new Map()\r\n    let dfs = function(paths, sum, index) {\r\n        if(sum \u003e target || index \u003e candidates.length) return\r\n        if(target === sum) {\r\n            res.push(paths)\r\n            return \r\n        }\r\n        // 计算当前数可选的倍数\r\n        let count = Math.floor((target-sum)/candidates[index])\r\n        // 选择当前数\r\n        for(let i = 0; i \u003c= count; i++) {\r\n            dfs(new Array(i).fill(candidates[index]).concat(paths), sum+i*candidates[index], index+1)\r\n        }\r\n    }\r\n    dfs([], 0, 0)\r\n    return res\r\n};\r\n```\r\n优化：\r\n```javascript\r\nvar combinationSum = function(candidates, target) {\r\n    let res = [], map = new Map()\r\n    let dfs = function(paths, sum, index) {\r\n        if(sum \u003e target || index \u003e candidates.length) return\r\n        if(target === sum) {\r\n            res.push(paths)\r\n            return \r\n        }\r\n        dfs(paths, sum, index+1)\r\n        if(target-sum\u003e=candidates[index]) {\r\n          dfs([...paths, candidates[index]], sum+candidates[index], index)\r\n        }\r\n    }\r\n    dfs([], 0, 0)\r\n    return res\r\n};\r\n```\r\n\r\n\r\n","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2022-04-06T15:49:54.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/170/JavaScript-Algorithms/issues/170"}