var letterCombinations = function(digits) {
const phoneMap = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz'
}
let res = []
let path = []
const backtrack = (index) => {
if(path.length === digits.length) {
res.push([...path].join(''))
return
}
const cur = phoneMap[digits[index]]
for(let i = 0; i < cur.length; i++) {
path.push(cur[i])
backtrack(index+1)
path.pop()
}
}
backtrack(0)
return res
};- 时间复杂度：O(3ᵐ × 4ⁿ)，m 个映射 3 字母的数字，n 个映射 4 字母的数字
- 空间复杂度：O(m + n)，递归深度 + path（不含 res 结果集）
关键套路：每层选不同按键的字母，选择池天然不重叠，不需要 used 也不需要 start；index 当层指针即可。
var generateParenthesis = function (n) {
const res = []
const backtrack = (str, left, right) => {
if (n * 2 === str.length) {
res.push(str)
return
}
if (left < n) {
backtrack(str + '(', left + 1, right)
}
if (right < left) {
backtrack(str + ')', left, right + 1)
}
}
backtrack('', 0, 0)
return res
};- 时间复杂度：O(4ⁿ / √n)，第 n 个卡特兰数 × 每个方案长 2n
- 空间复杂度：O(n)，递归深度
关键套路：隐式回溯——传参 str + '(' 利用字符串不可变性由系统栈自动撤销；两条剪枝约束：左括号没用完才能加左，右括号少于左括号才能加右。
var combinationSum = function(candidates, target) {
const res = []
const path = []
candidates.sort((a, b) => a -b)
const backtrack = (index, remind) => {
if(remind === 0) {
res.push([...path])
}
for(let i = index; i< candidates.length;i++) {
if(candidates[i] > remind) break
path.push(candidates[i])
backtrack(i, remind-candidates[i])
path.pop()
}
}
backtrack(0, target)
return res
};- 时间复杂度：O(nᵀ)，T = target / 最小候选值（搜索树上界）
- 空间复杂度：O(T)，递归深度
关键套路：数字可重复选 → 递归传 i 而不是 i + 1；先排序再用 candidates[i] > remind 提前 break 剪枝。
var permute = function (nums) {
const res = []
const used = new Array(nums.length).fill(false)
const path = []
const backtrack = () => {
if (path.length === nums.length) {
res.push([...path])
return
}
for (let i = 0; i < nums.length; i++) {
if (!used[i]) {
path.push(nums[i])
used[i] = true
backtrack()
used[i] = false
path.pop()
}
}
}
backtrack()
return res
};- 时间复杂度：O(n!·n)，n! 个排列，每个拷贝 path 花费 O(n)
- 空间复杂度：O(n)，used 数组 + 递归深度
关键套路：每层要回头选所有元素，顺序交换算不同方案 → 必须 used[] 按下标标记；与 77 组合对照记忆。
var combine = function(n, k) {
const res = []
const path = []
const backtrack = (start) => {
// 收网条件放函数开头：进函数先看是否选满
if (path.length === k) {
res.push([...path])
return
}
for (let i = start; i <= n; i++) {
path.push(i)
backtrack(i + 1) // 组合：只往后选，下一层从 i+1 开始，天然不会重选
path.pop()
}
}
backtrack(1)
return res
};- 时间复杂度：O(k × C(n,k))，C(n,k) 个组合，每个拷贝花费 O(k)
- 空间复杂度：O(k)，递归深度 + path
关键套路：组合/子集类不需要 used——start 指针只向后走，天然防重；全排列每层要回头选所有元素，才需要 used 标记。
var subsets = function(nums) {
const res = []
const path = []
const backtrack = (start) => {
res.push([...path]) // 与组合唯一区别：每个节点都是答案，不等选满
for (let i = start; i < nums.length; i++) {
path.push(nums[i])
backtrack(i + 1)
path.pop()
}
}
backtrack(0)
return res
};- 时间复杂度：O(n·2ⁿ)，2ⁿ 个子集，每个拷贝花费 O(n)
- 空间复杂度：O(n)，递归深度 + path
关键套路：和 77 组合同一模板——区别仅在收网时机：组合选满 k 个才收，子集进函数就收。
var exist = function(board, word) {
// 前置剪枝：字母频率不够，直接不用搜
const boardCounts = {}
for (const row of board)
for (const ch of row)
boardCounts[ch] = (boardCounts[ch] || 0) + 1
const wordCounts = {}
for (const ch of word) {
wordCounts[ch] = (wordCounts[ch] || 0) + 1
if (wordCounts[ch] > (boardCounts[ch] || 0)) return false
}
const rows = board.length, cols = board[0].length
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
const find = (i, j, k) => {
// 越界或不匹配：此路不通
if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[k]) return false
if (k === word.length - 1) return true // 最后一个字符也匹配上了
const cur = board[i][j]
board[i][j] = '' // 标记：棋盘自己当 used
for (const [di, dj] of dirs) {
if (find(i + di, j + dj, k + 1)) return true
}
board[i][j] = cur // 还原：对称撤销，和 path.pop() 一个道理
return false
}
for (let i = 0; i < rows; i++)
for (let j = 0; j < cols; j++)
if (find(i, j, 0)) return true
return false
};- 时间复杂度：O(M·N·3ᴸ)，每个起点扩散，走过后不能回头，每步至多 3 个新方向
- 空间复杂度：O(L)，递归深度
关键套路：网格回溯——棋盘自身当 used（进入时改、返回时还原，与 push/pop 对称）；前置频率统计可 O(MN+L) 直接剪掉不可能的用例。