穷举vs暴搜vs深搜vs回溯vs剪枝（典型算法思想）—— OJ例题算法解析思路

回溯算法的模版

void backtrack(vector<int>& path, vector<int>& choice, ...) 
{// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i = 0; i < choices.size(); i++) {// 做出选择path.push_back(choices[i]);// 做出当前选择后继续搜索backtrack(path, choices);// 撤销选择path.pop_back();}
}

目录

回溯算法的模版

一、46. 全排列 - 力扣（LeetCode）

算法代码：

1. 类的成员变量

2. permute 函数

3. dfs 函数

4. 回溯的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本

总结

二、78. 子集 - 力扣（LeetCode） 

递归流程：

解法一：算法代码（剪枝->回溯->递归出口） 

1. 类的成员变量

2. subsets 函数

3. dfs 函数

4. 回溯的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本（避免重复子集）

改进点：

8. 总结

解法二：算法代码（回溯->剪枝->递归出口）

1. 类的成员变量

2. subsets 函数

3. dfs 函数

4. 代码的核心思想

5. 代码的优化空间

6. 代码的复杂度分析

7. 代码的改进版本（避免重复子集）

改进点：

8. 总结

---

一、46. 全排列 - 力扣（LeetCode）

算法代码：

class Solution {vector<vector<int>> ret;vector<int> path;bool check[7];public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums) {if (path.size() == nums.size()) {ret.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (!check[i]) {path.push_back(nums[i]);check[i] = true;dfs(nums);// 回溯 -> 恢复现场path.pop_back();check[i] = false;}}}
};

1. 类的成员变量

• ret：用于存储所有可能的排列结果，类型为 vector<vector<int>>。

• path：用于存储当前正在构建的排列，类型为 vector<int>。

• check：用于标记某个元素是否已经被使用过，类型为 bool 数组，大小为 7（假设输入数组的长度不超过 7）。

2. permute 函数

• 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的排列。

• 调用 dfs(nums) 开始深度优先搜索。

• 最终返回 ret，即所有排列的结果。

3. dfs 函数

• 这是递归函数，用于生成所有可能的排列。

• 递归终止条件：如果 path 的大小等于 nums 的大小，说明当前 path 已经是一个完整的排列，将其加入到 ret 中，并返回。

• 递归过程：

  • 遍历 nums 数组中的每一个元素。

  • 如果当前元素没有被使用过（check[i] == false），则将其加入到 path 中，并标记为已使用。

  • 递归调用 dfs，继续生成下一个位置的元素。

  • 回溯：在递归返回后，撤销当前的选择（即从 path 中移除最后一个元素，并将 check[i] 重新标记为未使用），以便尝试其他可能的排列。

4. 回溯的核心思想

• 回溯是一种通过递归来尝试所有可能的选择，并在每一步撤销选择以回到上一步的算法。

• 在这段代码中，回溯体现在 path.pop_back() 和 check[i] = false 这两行代码上。它们的作用是撤销当前的选择，以便尝试其他可能的排列。

5. 代码的优化空间

• check 数组的大小是固定的 7，这意味着如果 nums 的大小超过 7，代码将无法正确处理。可以将 check 数组的大小动态设置为 nums.size()。

• 可以使用 std::swap 来直接在原数组上进行排列，从而减少 path 和 check 的使用，进一步优化空间复杂度。

6. 代码的复杂度分析

• 时间复杂度：O(n!)，其中 n 是 nums 的大小。因为全排列的数量是 n!。

• 空间复杂度：O(n!)，用于存储所有排列的结果。递归栈的深度为 n，因此递归的空间复杂度为 O(n)。

7. 代码的改进版本

class Solution {vector<vector<int>> ret;public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int start) {if (start == nums.size()) {ret.push_back(nums);return;}for (int i = start; i < nums.size(); i++) {swap(nums[start], nums[i]);dfs(nums, start + 1);swap(nums[start], nums[i]); // 回溯}}
};

在这个改进版本中，我们直接在原数组上进行排列，减少了 path 和 check 的使用，从而优化了空间复杂度。

总结

这段代码通过深度优先搜索和回溯的思想，实现了全排列的生成。代码的核心在于递归和回溯的处理，通过撤销选择来尝试所有可能的排列。

二、78. 子集 - 力扣（LeetCode） 

递归流程：

解法一：算法代码（剪枝->回溯->递归出口） 

// 解法⼀：
class Solution {vector<vector<int>> ret;vector<int> path;public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos) {if (pos == nums.size()) {ret.push_back(path);return;}// 选path.push_back(nums[pos]);dfs(nums, pos + 1);path.pop_back(); // 恢复现场// 不选dfs(nums, pos + 1);}
};

1. 类的成员变量

• ret：用于存储所有子集的结果，类型为 vector<vector<int>>。

• path：用于存储当前正在构建的子集，类型为 vector<int>。

---

2. subsets 函数

• 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的子集。

• 调用 dfs(nums, 0) 开始深度优先搜索，0 表示从数组的第一个元素开始处理。

• 最终返回 ret，即所有子集的结果。

---

3. dfs 函数

• 这是递归函数，用于生成所有可能的子集。

• 递归终止条件：如果 pos 等于 nums 的大小，说明已经处理完所有元素，此时 path 中存储的就是一个子集，将其加入到 ret 中，并返回。

• 递归过程：

  1. 选择当前元素：

     • 将 nums[pos] 加入到 path 中。

     • 递归调用 dfs(nums, pos + 1)，继续处理下一个元素。

     • 在递归返回后，撤销选择（即从 path 中移除最后一个元素），以便尝试不选择当前元素的情况。

  2. 不选择当前元素：

     • 直接递归调用 dfs(nums, pos + 1)，跳过当前元素，继续处理下一个元素。

---

4. 回溯的核心思想

• 回溯是一种通过递归来尝试所有可能的选择，并在每一步撤销选择以回到上一步的算法。

• 在这段代码中，回溯体现在 path.pop_back() 这一行代码上。它的作用是撤销当前的选择，以便尝试不选择当前元素的情况。

---

5. 代码的优化空间

• 如果输入数组 nums 中包含重复元素，这段代码会生成重复的子集。可以通过排序和剪枝来避免重复子集的生成。

• 可以将 path 改为引用传递，减少拷贝的开销。

---

6. 代码的复杂度分析

• 时间复杂度：O(2^n)，其中 n 是 nums 的大小。因为每个元素有两种选择（选或不选），总共有 2^n 个子集。

• 空间复杂度：O(n)，递归栈的深度为 n。结果存储空间不计入空间复杂度。

---

7. 代码的改进版本（避免重复子集）

如果输入数组 nums 中包含重复元素，可以通过排序和剪枝来避免生成重复的子集。改进后的代码如下：

class Solution {vector<vector<int>> ret;vector<int> path;public:vector<vector<int>> subsets(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序，便于剪枝dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos) {ret.push_back(path); // 每次递归都加入当前子集for (int i = pos; i < nums.size(); i++) {if (i > pos && nums[i] == nums[i - 1]) continue; // 剪枝，避免重复path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back(); // 回溯}}
};

改进点：

1. 排序：先对 nums 排序，使得相同的元素相邻。

2. 剪枝：在递归过程中，如果当前元素和前一个元素相同，并且不是第一次遇到该元素，则跳过，避免重复子集。

3. 提前加入子集：在每次递归开始时，直接将当前 path 加入到 ret 中，这样可以避免在递归终止时才加入子集。

---

8. 总结

        这段代码通过深度优先搜索和回溯的思想，实现了求解数组的所有子集。代码的核心在于对每个元素的选择和不选择两种情况的分支处理，并通过回溯撤销选择以尝试其他可能性。如果输入数组包含重复元素，可以通过排序和剪枝来优化，避免生成重复子集。

解法二：算法代码（回溯->剪枝->递归出口）

// 解法⼆：
class Solution {vector<vector<int>> ret;vector<int> path;public:vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos) {ret.push_back(path);for (int i = pos; i < nums.size(); i++) {path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back(); // 恢复现场}}
};

1. 类的成员变量

• ret：用于存储所有子集的结果，类型为 vector<vector<int>>。

• path：用于存储当前正在构建的子集，类型为 vector<int>。

---

2. subsets 函数

• 这是主函数，接收一个整数数组 nums 作为输入，并返回所有可能的子集。

• 调用 dfs(nums, 0) 开始深度优先搜索，0 表示从数组的第一个元素开始处理。

• 最终返回 ret，即所有子集的结果。

---

3. dfs 函数

• 这是递归函数，用于生成所有可能的子集。

• 递归过程：

  1. 将当前子集加入结果：

     • 在每次递归调用开始时，直接将当前 path 加入到 ret 中。这是因为 path 在每一层递归中都表示一个有效的子集。

  2. 遍历数组元素：

     • 从当前位置 pos 开始遍历 nums 数组。

     • 将当前元素 nums[i] 加入到 path 中，表示选择该元素。

     • 递归调用 dfs(nums, i + 1)，继续处理下一个元素。

     • 在递归返回后，撤销选择（即从 path 中移除最后一个元素），以便尝试其他可能的子集。

---

4. 代码的核心思想

• 子集的生成：

  • 子集的生成可以看作是对每个元素的选择或不选择。

  • 通过递归和回溯，代码枚举了所有可能的选择组合。

• 提前加入子集：

  • 在每次递归调用开始时，直接将当前 path 加入到 ret 中。这是因为 path 在每一层递归中都表示一个有效的子集，无需等到递归终止才加入。

---

5. 代码的优化空间

• 如果输入数组 nums 中包含重复元素，这段代码会生成重复的子集。可以通过排序和剪枝来避免重复子集的生成。

• 可以将 path 改为引用传递，减少拷贝的开销。

---

6. 代码的复杂度分析

• 时间复杂度：O(2^n)，其中 n 是 nums 的大小。因为每个元素有两种选择（选或不选），总共有 2^n 个子集。

• 空间复杂度：O(n)，递归栈的深度为 n。结果存储空间不计入空间复杂度。

---

7. 代码的改进版本（避免重复子集）

如果输入数组 nums 中包含重复元素，可以通过排序和剪枝来避免生成重复的子集。改进后的代码如下：

class Solution {vector<vector<int>> ret;vector<int> path;public:vector<vector<int>> subsets(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序，便于剪枝dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos) {ret.push_back(path); // 将当前子集加入结果for (int i = pos; i < nums.size(); i++) {if (i > pos && nums[i] == nums[i - 1]) continue; // 剪枝，避免重复path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back(); // 回溯}}
};

改进点：

1. 排序：先对 nums 排序，使得相同的元素相邻。

2. 剪枝：在递归过程中，如果当前元素和前一个元素相同，并且不是第一次遇到该元素，则跳过，避免重复子集。

---

8. 总结

        这段代码通过深度优先搜索和回溯的思想，实现了求解数组的所有子集。与解法一相比，解法二的代码更加简洁，直接通过循环和递归来生成所有子集。如果输入数组包含重复元素，可以通过排序和剪枝来优化，避免生成重复子集。代码的核心思想是对每个元素的选择和不选择进行枚举，并通过回溯撤销选择以尝试其他可能性。

---

重点：

递归的本质

        递归是一种通过函数调用自身来解决问题的编程技巧。在递归过程中，问题的规模会逐渐减小，直到达到一个终止条件。递归的核心思想是分治，即将一个大问题分解为若干个小问题，然后分别解决这些小问题。

在子集问题中，递归的作用是对每个元素做出决策（选或不选），从而生成所有可能的子集。

---

为什么解法一不需要 for 循环？

在解法一中，递归的逻辑是对每个元素做出“选”或“不选”的决策。具体来说：

1. 对于当前元素 nums[pos]，有两种选择：

   • 选择它：将其加入 path，然后递归处理下一个元素（pos + 1）。

   • 不选择它：直接递归处理下一个元素（pos + 1）。

2. 递归的终止条件是 pos == nums.size()，表示已经处理完所有元素。

这种递归逻辑已经隐含了对所有元素的遍历，因此不需要显式的 for 循环。

---

为什么解法二需要 for 循环？

在解法二中，递归的逻辑是显式地遍历数组中的元素，依次生成子集。具体来说：

1. for 循环从 pos 开始遍历数组 nums，表示从当前位置开始选择元素。

2. 对于每个元素 nums[i]，将其加入 path，然后递归处理下一个元素（i + 1）。

3. 在递归返回后，通过 path.pop_back() 回溯，恢复现场，尝试下一个元素。

这种递归逻辑通过 for 循环显式地遍历元素，确保每个元素都有机会被选中，并且避免生成重复的子集。

---

递归和 for 循环的关系

• 递归的本质是遍历：递归确实可以遍历所有元素，但遍历的方式可以是隐式的（如解法一）或显式的（如解法二）。

• 是否需要 for 循环：取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历（如解法一），则不需要 for 循环；如果需要显式地遍历元素（如解法二），则需要 for 循环。

---

两种解法的对比

特性	解法一（无 for 循环）	解法二（有 for 循环）
递归逻辑	对每个元素做出“选”或“不选”的决策	显式遍历元素，生成子集
是否需要 for 循环	否	是
代码结构	更简洁	更直观
时间复杂度	O(2^n)	O(2^n)

---

为什么解法二需要 for 循环？

解法二的递归逻辑是通过 for 循环显式地遍历元素，确保每个元素都有机会被选中，并且避免生成重复的子集。具体来说：

1. 显式遍历元素：for 循环从 pos 开始遍历数组 nums，表示从当前位置开始选择元素。

2. 避免重复子集：通过 for 循环从 pos 开始遍历，可以避免生成重复的子集。例如，如果已经选择了 nums[1]，那么后续的子集只能从 nums[2] 开始选择，而不能回头选择 nums[0]。

3. 生成所有子集：通过 for 循环和递归的结合，确保所有可能的子集都被生成。

---

总结

• 递归确实可以遍历所有元素，但遍历的方式可以是隐式的（如解法一）或显式的（如解法二）。

• 是否需要 for 循环取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历，则不需要 for 循环；如果需要显式地遍历元素，则需要 for 循环。

• 解法一和解法二都是正确的，只是它们的递归逻辑和实现方式不同。解法一更简洁，解法二更直观。