案例

电话号码的字母组合（中）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

解题思路

1. 初始化：首先，获取输入数字字符串的长度 k 和一个映射 map，其中每个数字映射到它对应的字母。
2. 边界条件处理：
   • 如果 k 为 0（即没有输入数字），直接返回空数组。
   • 如果 k 为 1，返回该数字对应的字母数组。
3. 回溯算法：
   • 定义一个结果数组 res 和一个路径数组 path。
   • 调用回溯函数 backtracking，开始递归搜索所有可能的字母组合。
   • 在回溯函数中，如果当前路径的长度等于数字字符串的长度，将路径加入结果数组。
   • 否则，遍历当前数字对应的每个字母，将其加入路径，并递归调用回溯函数处理下一个数字。
   • 每次递归完成后，通过 path.pop() 进行回溯，移除路径中的最后一个字母，以便尝试其他可能的字母组合。
4. 返回结果：函数最终返回包含所有可能字母组合的结果数组 res。

这个算法的核心是回溯，它通过递归和回溯来探索所有可能的字母组合，并在满足条件时将它们添加到结果数组中。

var letterCombinations = function (digits) {
    const k = digits.length; // 获取输入数字字符串的长度
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]; // 映射每个数字到对应的字母
    if (!k) return []; // 如果长度为0，直接返回空数组
    if (k === 1) return map[digits].split(""); // 如果长度为1，返回该数字对应的字母数组

    const res = [], path = []; // res用于存储最终结果，path用于存储当前组合
    backtracking(digits, k, 0); // 调用回溯函数
    return res; // 返回最终结果

    function backtracking(n, k, a) {
        if (path.length === k) { // 如果当前组合的长度等于数字字符串的长度
            res.push(path.join("")); // 将当前组合加入结果数组
            return;
        }
        for (const v of map[n[a]]) { // 遍历当前数字对应的每个字母
            path.push(v); // 将字母加入当前组合
            backtracking(n, k, a + 1); // 递归调用回溯函数，处理下一个数字
            path.pop(); // 回溯，移除最后一个字母
        }
    }
};

组合(中)

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

解题思路

首先，我们有两个主要的函数：combine 和 combineHelper。

1. combine 函数是外部接口，它初始化结果数组 result，并调用 combineHelper 函数来生成组合。
2. combineHelper 函数是实现回溯算法的核心。它接受三个参数：n（总数），k（要选择的元素数量），和 startIndex（开始选择的索引）。
   • 如果 path 数组的长度等于k，意味着我们已经选择了k个元素，这时我们将这个组合添加到结果数组 result 中。
   • 接下来是一个循环，从 startIndex 开始，到 n - (k - path.length) + 1 结束。这个循环用于选择下一个元素。这里使用了剪枝技术：因为只需要k个元素，所以一旦剩下的元素数量不足以填满组合，就没有必要继续了。

在每次循环中，算法将当前元素 i 添加到 path 数组中，并递归调用 combineHelper，将 startIndex 设置为 i + 1，这意味着下一次选择将从 i 的下一个元素开始。递归调用后，算法将 i 从 path 数组中移除，这是回溯的关键步骤，它允许算法回退并尝试其他可能的组合。

参考链接

// combine函数：生成从n个元素中选取k个元素的组合
let result = [] // 存储最终结果的数组
let path = [] // 存储当前组合的数组
var combine = function (n, k) {
    result = [] // 初始化结果数组
    combineHelper(n, k, 1) // 调用辅助函数开始生成组合
    return result // 返回最终结果
};

// combineHelper函数：使用回溯法和剪枝技术生成组合
const combineHelper = (n, k, startIndex) => {
    if (path.length === k) {
        // 如果当前组合的长度等于k，将其添加到结果数组中
        result.push([...path])
        return
    }
    for (let i = startIndex; i <= n - (k - path.length) + 1; ++i) {
        // 从startIndex开始，循环到n-(k-path.length)+1，进行剪枝
        path.push(i) // 将当前元素添加到path中
        combineHelper(n, k, i + 1) // 递归调用，startIndex更新为i+1
        path.pop() // 回溯：移除最后一个元素，尝试其他可能的组合
    }
}

全排列（中）

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

解题思路

image.png

1. 初始化：创建两个数组res和path，分别用于存储所有排列和当前排列。
2. 回溯函数：定义一个名为backtracking的函数，它接受三个参数：n（数字数组），k（数组长度），used（用于标记已使用的数字）。
3. 终止条件：如果path的长度等于k，说明找到了一个排列，将其加入res。
4. 递归过程：
   • 遍历数字数组n。
   • 如果当前数字已使用（used[i]为true），则跳过。
   • 将当前数字加入path，并标记为已使用。
   • 递归调用backtracking函数，寻找下一个数字。
   • 回溯：将最后一个数字从path中移除，并标记为未使用。

这个算法通过递归和回溯，生成输入数组所有可能的排列。

参考链接

/**
 * @param {number[]} nums - 输入的数字数组
 * @return {number[][]} - 返回数字数组所有可能的排列
 */
var permute = function (nums) {
    const res = [], path = []; // res用于存储所有排列，path用于存储当前排列
    backtracking(nums, nums.length, []); // 调用回溯函数
    return res; // 返回所有排列

    // 回溯函数
    function backtracking(n, k, used) {
        if (path.length === k) { // 如果path长度等于nums长度，说明找到一个排列
            res.push(Array.from(path)); // 将当前排列加入res
            return;
        }
        for (let i = 0; i < k; i++) {
            if (used[i]) continue; // 如果当前数字已使用，跳过
            path.push(n[i]); // 将当前数字加入path
            used[i] = true; // 标记当前数字已使用
            backtracking(n, k, used); // 递归寻找下一个数字
            path.pop(); // 回溯，移除最后一个数字
            used[i] = false; // 标记当前数字未使用
        }
    }
};

优化

1. 去除used数组：在这个特定的实现中，used数组并不是必需的。因为数组nums中的元素是唯一的，我们可以通过检查path数组中是否已经包含当前元素来决定是否继续递归。
2. 减少递归调用：在当前实现中，每次递归都会遍历整个数组。实际上，我们可以通过交换元素的方式来避免递归时遍历已处理过的元素。

为什么交换元素可以避免重复使用同一个元素？

交换元素可以避免重复使用同一个元素，是因为它确保了在每一步递归中，我们只处理一个分支上的元素，从而避免了不同分支之间的元素交叉使用。这是回溯算法中的一个关键概念，称为“路径分隔”。
在回溯算法中，我们通常通过递归遍历所有可能的分支来找到所有解。每个分支代表一种可能的选择。为了避免重复，我们需要确保一旦一个元素在一个分支上被使用，它就不会在另一个分支上再次被使用。这就是交换元素的目的。
具体来说，当我们在递归函数中交换两个元素时，我们实际上是在创建一个新的分支。在这个新分支中，被交换到当前位置的元素被视为“已使用”，而原本在那个位置的元素则被视为“未使用”。这样，每个分支都有其独特的元素状态，从而避免了重复使用。
例如，考虑一个数组[1, 2, 3]。在第一次递归中，我们可以交换1和2，得到[2, 1, 3]。这时，2被视为已使用，而1被视为未使用。在接下来的递归中，我们只处理[1, 3]这部分，因为2已经在当前分支上被使用过了。这样，我们就避免了在同一个分支上重复使用2。
通过这种方式，交换元素帮助我们维持了每个分支的独立性，确保了每个元素在每个排列中只被使用一次。这是回溯算法中处理排列问题时避免重复的关键机制。

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, 0);
    return res;

    function backtracking(n, index) {
        if (index === n.length) {
            res.push(Array.from(path));
            return;
        }
        for (let i = index; i < n.length; i++) {
            // 交换元素
            [n[i], n[index]] = [n[index], n[i]];
            path.push(n[index]);
            backtracking(n, index + 1);
            // 回溯，恢复交换
            [n[i], n[index]] = [n[index], n[i]];
            path.pop();
        }
    }
};

组合总和（中）

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: [] 

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

解题思路

1. 排序：首先对给定的候选数组candidates进行排序。这样做的好处是可以在后续的递归过程中提前终止循环，提高效率。
2. 初始化结果和路径数组：创建两个数组res和path。res用于存储所有满足条件的组合，path用于存储当前的组合。
3. 回溯函数：定义一个名为backtracking的函数，它接受两个参数：start和sum。start表示当前递归开始的位置，sum表示当前组合的元素之和。
4. 递归终止条件：如果sum等于目标值target，则将当前的path添加到res中，并返回。
5. 循环遍历：从start开始遍历candidates数组。对于每个元素n，执行以下操作：
   • 如果n大于target - sum，则提前终止循环，因为后面的元素都会大于target - sum。
   • 将n添加到path中，更新sum。
   • 递归调用backtracking函数，传入i和更新后的sum，这样可以保证每个元素都可以被重复使用。
   • 回溯：将n从path中移除，恢复sum的值。
6. 返回结果：当所有递归调用完成后，返回res数组，它包含了所有满足条件的组合。

这个算法的关键在于递归和回溯的过程，通过不断地尝试和撤销操作，找出所有可能的组合。排序和提前终止循环是提高效率的关键优化。

var combinationSum = function (candidates, target) {
    const res = [], path = [];
    candidates.sort((a, b) => a - b); // 排序
    backtracking(0, 0);
    return res;

    function backtracking(start, sum) {
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            const n = candidates[i];
            if (n > target - sum) break; // 提前终止条件
            path.push(n);
            sum += n;
            backtracking(i, sum); // 从i开始，避免重复
            path.pop();
            sum -= n;
        }
    }
};

N 皇后 II（难）

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

img

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

解题思路

回溯

1. 函数定义：
   • totalNQueens(n) 是主函数，接收一个参数 n，表示棋盘的大小。
   • ans 是用来计数解决方案的变量。
   • on_path、diag1 和 diag2 是三个布尔数组，用来标记哪些位置上已经放置了皇后。
2. 辅助数组：
   • on_path：长度为 n 的数组，用来标记每一列上是否已经放置了皇后。
   • diag1 和 diag2：长度为 2n-1 的数组，分别用来标记两个主对角线方向上是否已经放置了皇后。
3. dfs函数：
   • dfs(r) 是一个递归函数，用来在棋盘上放置皇后。
   • 参数 r 表示当前行。
   • 如果 r === n，说明已经放置完所有皇后，此时找到一个解决方案，ans 加一。
   • 循环遍历每一列，尝试在该列上放置皇后。
   • 使用三个布尔数组来检查当前位置是否可以放置皇后。
   • 如果可以放置，更新三个布尔数组，并递归调用 dfs(r + 1)。
   • 递归完成后，恢复现场，即回溯到上一步的状态。
4. 主函数调用：
   • 调用 dfs(0) 开始递归搜索。
   • 最后返回 ans，即所有可能的解决方案的数量。

这个算法的核心思想是“试错”，它尝试在每一行放置一个皇后，然后检查是否与已经放置的皇后冲突。如果不冲突，就继续在下一行放置；如果冲突，就尝试下一列。通过这样的方式，它可以找到所有可能的解决方案。

位运算

• solve 函数：这是递归函数，用于在棋盘上放置皇后。
  • 参数 n 是棋盘的大小。
  • 参数 row 是当前行。
  • 这行代码是N皇后问题中使用位运算的关键部分。它的作用是计算在当前行中，哪些位置可以放置皇后。这个计算是基于之前放置的皇后的位置来进行的，以确保新放置的皇后不会与已经放置的皇后发生冲突。下面我将详细解释这行代码：

    let availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
    

    1. 1 << n：这表示将数字1左移n位。在二进制表示中，这会产生一个数，其最高位是1，其余位都是0。例如，如果 n = 3，则 1 << 3 的二进制表示是 1000。
    2. ((1 << n) - 1)：这个表达式计算出一个二进制数，其所有位都是1（除了最高位是0）。这个数表示了棋盘上所有可能的位置。例如，如果 n = 3，则 ((1 << 3) - 1) 的二进制表示是 0111。
    3. columns | diagonals1 | diagonals2：这个表达式是将三个变量 columns、diagonals1 和 diagonals2 进行按位或操作。这三个变量分别表示列、两个对角线的占用情况。在二进制表示中，如果某个位是1，则表示相应的位置上已经放置了皇后。
    4. ~(columns | diagonals1 | diagonals2)：这个表达式是对上面的结果进行按位取反。在二进制表示中，如果某个位是0，则表示相应的位置上已经放置了皇后；如果某个位是1，则表示相应的位置是空的。
    5. ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2))：这个表达式是将上面计算出的所有可能的位置与不可用的位置进行按位与操作。在二进制表示中，结果中的每个1都表示一个可以放置皇后的位置。
       综上所述，这行代码计算出了在当前行中，哪些位置可以放置皇后，同时确保新放置的皇后不会与已经放置的皇后发生冲突。这种方法非常高效，因为它直接在位级别上进行操作，避免了不必要的循环和条件判断。
  • 参数 columns、diagonals1 和 diagonals2 分别表示列、两个对角线的占用情况。
  • 如果 row === n，说明已经放置完所有皇后，返回1（找到一个解决方案）。
  • 计算当前行可用的位置 availablePositions。
  • 循环遍历所有可用的位置，递归调用 solve 函数，并更新列、对角线的占用情况。
  • 返回当前行的解决方案总数。

这个算法的核心思想是通过位运算高效地检查和更新皇后的位置状态，从而找到所有可能的解决方案。

回溯

var totalNQueens = function (n) {
    let ans = 0; // 用于计数所有可能的解决方案
    let on_path = Array(n).fill(false); // 标记每一列上是否已经放置了皇后
    let diag1 = Array(n * 2 - 1).fill(false); // 标记其中一个主对角线方向上是否已经放置了皇后
    let diag2 = Array(n * 2 - 1).fill(false); // 标记另一个主对角线方向上是否已经放置了皇后

    // dfs函数：递归地在棋盘上放置皇后
    function dfs(r) {
        if (r === n) { // 如果已经放置完所有皇后
            ans++; // 找到一个解决方案，计数加一
            return; // 返回上一层递归
        }
        for (let c = 0; c < n; ++c) { // 遍历每一列
            const rc = r - c + n - 1; // 计算对角线上的索引
            // 检查当前位置是否可以放置皇后
            if (!on_path[c] && !diag1[r + c] && !diag2[rc]) {
                on_path[c] = diag1[r + c] = diag2[rc] = true; // 更新标记
                dfs(r + 1); // 递归地在下一行放置皇后
                on_path[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场，即回溯
            }
        }
    }
    dfs(0); // 从第一行开始递归搜索
    return ans; // 返回所有可能的解决方案的数量
};

位运算

const solve = (n, row, columns, diagonals1, diagonals2) => {
    if (row === n) {
        return 1; // 如果所有行都放置了皇后，则找到一个解决方案
    } else {
        let count = 0;
        let availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
        // 计算可用的位置，即当前行中没有被列、对角线占用的位置
        while (availablePositions != 0) {
            const position = availablePositions & (-availablePositions); // 获取最低位的1
            availablePositions = availablePositions & (availablePositions - 1); // 移除最低位的1
            // 递归到下一行，并更新列、对角线的占用情况
            count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
        }
        return count; // 返回当前行的解决方案总数
    }
}
var totalNQueens = function (n) {
    return solve(n, 0, 0, 0, 0); // 从第一行开始递归搜索
};

括号生成(中)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解题思路

1. 初始化：设置结果数组ans和当前路径数组path，长度为2n。
2. 深度优先搜索（DFS）
   • 递归终止条件：当构建的字符串长度达到2n时，将当前路径加入结果数组。
   • 递归过程
     • 如果当前开括号数量open小于n，可以添加开括号，并递归调用dfs。
     • 如果当前闭括号数量（i - open）小于开括号数量open，可以添加闭括号，并递归调用dfs。
3. 返回结果：返回包含所有合法括号组合的数组ans。

这个算法通过递归和回溯的方式，有效地遍历了所有可能的括号组合，并确保了生成的每个组合都是合法的。

var generateParenthesis = function (n) {
    const m = n * 2; // 结果字符串的长度是n对括号，所以是2n
    let ans = []; // 用于存储所有合法的括号组合
    let path = Array(m); // 用于构建当前的括号组合

    // 定义深度优先搜索函数
    function dfs(i, open) {
        if (i === n * 2) { // 当构建的字符串长度达到2n时，表示一个组合完成
            ans.push(path.join("")); // 将当前组合加入答案数组
            return;
        }
        if (open < n) { // 如果当前开括号的数量小于n，可以添加开括号
            path[i] = '('; // 在当前位置添加开括号
            dfs(i + 1, open + 1); // 继续递归，位置加1，开括号数量加1
        }
        if (i - open < open) { // 如果当前闭括号的数量小于开括号的数量，可以添加闭括号
            path[i] = ')'; // 在当前位置添加闭括号
            dfs(i + 1, open); // 继续递归，位置加1，开括号数量不变
        }
    }

    dfs(0, 0); // 从位置0开始，开括号数量为0
    return ans; // 返回所有合法的括号组合
};

单词搜索(中)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

img

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

img

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

img

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路

Kapture 2024-07-24 at 11.28.16

1. 初始化：定义网格的行数 m 和列数 n，创建一个同样大小的 visited 数组，用于跟踪每个单元格是否已被访问。

2. 深度优先搜索（DFS）：对于网格中的每个单元格，使用DFS算法搜索可能的路径。

   • 终止条件：如果当前单元格的索引越界、已被访问、或字符不匹配，则返回 false。
   • 成功条件：如果当前字符是单词的最后一个字符，并且与网格中的字符匹配，则返回 true。
   • 递归搜索：将当前单元格标记为已访问，然后递归地搜索上、下、左、右四个相邻单元格。如果任何一个方向返回 true，则整个搜索成功。
   • 回溯：在返回之前，将当前单元格标记为未访问，以便其他路径可以再次使用该单元格。

3. 遍历网格：从网格的第一个单元格开始，逐个检查每个单元格。对于每个单元格，调用DFS函数，如果DFS返回 true，则说明找到了单词，算法结束并返回 true。

4. 返回结果：如果遍历完整个网格都没有找到单词，则返回 false。

关键点：

• DFS：利用DFS来探索所有可能的路径。
• 回溯：在DFS过程中，通过回溯来撤销之前的操作，确保每个单元格在搜索不同路径时可以被重复使用。
• 剪枝：通过检查索引越界、已访问状态和字符匹配来提前终止不必要的搜索。

通过这种方式，算法能够有效地在二维网格中查找是否存在给定的单词。

var exist = function (board, word) {
    const m = board.length; // 获取网格的行数
    const n = board[0].length; // 获取网格的列数
    const visited = Array.from({ length: m }, () => Array(n).fill(false)); // 创建一个访问记录数组，初始所有值为false

    // 深度优先搜索函数
    const dfs = (i, j, k) => {
        // 剪枝：如果索引越界或当前单元格已访问或字符不匹配，返回false
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || board[i][j] !== word[k]) {
            return false;
        }
        // 如果已经匹配到单词的最后一个字符，返回true
        if (k === word.length - 1) {
            return true;
        }
        // 标记当前单元格为已访问
        visited[i][j] = true;
        // 递归地搜索上下左右四个方向
        const res = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
            dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
        // 回溯，将当前单元格标记为未访问
        visited[i][j] = false;
        // 返回搜索结果
        return res;
    };

    // 遍历网格中的每一个单元格
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 如果在当前位置找到了单词，返回true
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }
    // 如果遍历完整个网格都没有找到单词，返回false
    return false;
};