代码模板 let BFS = function (start, target) { let queue = []; // 核心数据结构 let visited = new Set(); // 避免走回头路 queue.push(start); // 将起点加入队列 visited.add(start); let step = 0; // 记录扩散的步数 while (queue.length !== 0) { let length = queue.length; /* 将当前队列中的所有节点向四周扩散 */ for (let i = 0; i < length; i++) { let cur = queue.shift(); /* 划重点：这里判断是否到达终点 */ if (cur === target) return step; /* 将 cur 的相邻节点加入队列 */ for (let x = 0; x < n; x++) { if (!visited.has(x)) { queue.push(x); visited.add(x); } } } /* 划重点：更新步数在这里 */ step++; }} 77. 组合 var combine = function (n, k) { // 返回的结果集 let result = [] // 单层遍历的结果 let path = [] const backtracking = (n, k, startIndex) => { // 当 path.length === k, 终止 if (path.length === k) { result.push([...path]) return } // 单层搜索 for (let i = startIndex; i <= n; ++i) { // 处理节点 path.push(i) // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始 backtracking(n, k, i + 1) path.pop() } } // 题目中说，从 1 开始遍历到 n backtracking(n, k, 1) return result}; 216. 组合总和 III var combinationSum3 = function (k, n) { let result = [] let path = [] let backtracking = (n, k, startIndex) => { if (path.length === k && path.reduce((a, b) => a + b) === n) { result.push([...path]) return } for (let i = startIndex; i <= 9; i++) { path.push(i) backtracking(n, k, i + 1) path.pop() } } backtracking(n, k, 1) return result}; 17. 电话号码的字母组合 var letterCombinations = function (digits) { const digitsLength = digits.length; // 创建一个结果集 const map = ["", "", "abc", "def", "ghi", "dddhb", "mno", "pqrs", "tuv", "wxyz"]; if (!digitsLength) return []; if (digitsLength === 1) return map[digits].split(""); let result = []; let path = []; const backtracking = (startIndex) => { if (path.length === digitsLength) { result.push(path.join("")); return; } for (const v of map[digits[startIndex]]) { path.push(v); backtracking(startIndex + 1); path.pop(); } } backtracking(0); return result;}; 39. 组合总和 var combinationSum = function (candidates, target) { let result = []; let path = []; let startIndex = 0; let sum = 0 let backtracking = (sum, startIndex) => { if (sum > target) { return; } if (sum === target) { result.push([...path]) return } for (let i = startIndex; i < candidates.length; i++) { sum += candidates[i]; path.push(candidates[i]); backtracking(sum, i); sum -= candidates[i]; path.pop(); } } backtracking(sum, startIndex) return result;}; 40. 组合总和 II var combinationSum2 = function (candidates, target) { let result = []; let path = []; let startIndex = 0; let sum = 0; let used = new Array(candidates.length).fill(false); candidates.sort(); let backtracking = (sum, startIndex) => { if (sum > target) { return; } if (sum === target) { result.push([...path]) return } for (let i = startIndex; i < candidates.length; i++) { if (candidates[i] === candidates[i - 1] && used[i - 1] == false) continue; sum += candidates[i]; path.push(candidates[i]); used[i] = true; backtracking(sum, i + 1, used); used[i] = false; sum -= candidates[i]; path.pop(); } } backtracking(sum, startIndex) return result;}; 131. 分割回文串 var partition = function (s) { let result = []; let path = []; let backtracking = (startIndex) => { if (startIndex === s.length) { result.push([...path]) } for (let i = startIndex; i < s.length; i++) { if (isPalindrome(s, startIndex, i)) { let str = s.substr(startIndex, i - startIndex + 1); path.push(str); } else { continue } backtracking(i + 1) path.pop(); } } backtracking(0); return result;};let isPalindrome = function (s, i, j) { while (i <= j) { if (s[i] !== s[j]) { return false; } i++; j--; } return true;}