云南 网站模版,网站数据库搬家,网站建设增城,临沧网络推广回溯算法的模版
void backtrack(vectorint path, vectorint choice, ...)
{// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i 0; i choices.size(); i) {// 做出选择…
回溯算法的模版
void backtrack(vectorint path, vectorint 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 {vectorvectorint ret;vectorint path;bool check[7];public:vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}void dfs(vectorint 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用于存储所有可能的排列结果类型为 vectorvectorint。 path用于存储当前正在构建的排列类型为 vectorint。 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 {vectorvectorint ret;public:vectorvectorint permute(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint 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 {vectorvectorint ret;vectorint path;public:vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint 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用于存储所有子集的结果类型为 vectorvectorint。 path用于存储当前正在构建的子集类型为 vectorint。 2. subsets 函数 这是主函数接收一个整数数组 nums 作为输入并返回所有可能的子集。 调用 dfs(nums, 0) 开始深度优先搜索0 表示从数组的第一个元素开始处理。 最终返回 ret即所有子集的结果。 3. dfs 函数 这是递归函数用于生成所有可能的子集。 递归终止条件如果 pos 等于 nums 的大小说明已经处理完所有元素此时 path 中存储的就是一个子集将其加入到 ret 中并返回。 递归过程 选择当前元素 将 nums[pos] 加入到 path 中。 递归调用 dfs(nums, pos 1)继续处理下一个元素。 在递归返回后撤销选择即从 path 中移除最后一个元素以便尝试不选择当前元素的情况。 不选择当前元素 直接递归调用 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 {vectorvectorint ret;vectorint path;public:vectorvectorint subsets(vectorint nums) {sort(nums.begin(), nums.end()); // 排序便于剪枝dfs(nums, 0);return ret;}void dfs(vectorint 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(); // 回溯}}
};
改进点 排序先对 nums 排序使得相同的元素相邻。 剪枝在递归过程中如果当前元素和前一个元素相同并且不是第一次遇到该元素则跳过避免重复子集。 提前加入子集在每次递归开始时直接将当前 path 加入到 ret 中这样可以避免在递归终止时才加入子集。 8. 总结 这段代码通过深度优先搜索和回溯的思想实现了求解数组的所有子集。代码的核心在于对每个元素的选择和不选择两种情况的分支处理并通过回溯撤销选择以尝试其他可能性。如果输入数组包含重复元素可以通过排序和剪枝来优化避免生成重复子集。 解法二算法代码回溯-剪枝-递归出口
// 解法⼆
class Solution {vectorvectorint ret;vectorint path;public:vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ret;}void dfs(vectorint 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用于存储所有子集的结果类型为 vectorvectorint。 path用于存储当前正在构建的子集类型为 vectorint。 2. subsets 函数 这是主函数接收一个整数数组 nums 作为输入并返回所有可能的子集。 调用 dfs(nums, 0) 开始深度优先搜索0 表示从数组的第一个元素开始处理。 最终返回 ret即所有子集的结果。 3. dfs 函数 这是递归函数用于生成所有可能的子集。 递归过程 将当前子集加入结果 在每次递归调用开始时直接将当前 path 加入到 ret 中。这是因为 path 在每一层递归中都表示一个有效的子集。 遍历数组元素 从当前位置 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 {vectorvectorint ret;vectorint path;public:vectorvectorint subsets(vectorint nums) {sort(nums.begin(), nums.end()); // 排序便于剪枝dfs(nums, 0);return ret;}void dfs(vectorint 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(); // 回溯}}
};
改进点 排序先对 nums 排序使得相同的元素相邻。 剪枝在递归过程中如果当前元素和前一个元素相同并且不是第一次遇到该元素则跳过避免重复子集。 8. 总结 这段代码通过深度优先搜索和回溯的思想实现了求解数组的所有子集。与解法一相比解法二的代码更加简洁直接通过循环和递归来生成所有子集。如果输入数组包含重复元素可以通过排序和剪枝来优化避免生成重复子集。代码的核心思想是对每个元素的选择和不选择进行枚举并通过回溯撤销选择以尝试其他可能性。 重点
递归的本质 递归是一种通过函数调用自身来解决问题的编程技巧。在递归过程中问题的规模会逐渐减小直到达到一个终止条件。递归的核心思想是分治即将一个大问题分解为若干个小问题然后分别解决这些小问题。
在子集问题中递归的作用是对每个元素做出决策选或不选从而生成所有可能的子集。 为什么解法一不需要 for 循环
在解法一中递归的逻辑是对每个元素做出“选”或“不选”的决策。具体来说 对于当前元素 nums[pos]有两种选择 选择它将其加入 path然后递归处理下一个元素pos 1。 不选择它直接递归处理下一个元素pos 1。 递归的终止条件是 pos nums.size()表示已经处理完所有元素。
这种递归逻辑已经隐含了对所有元素的遍历因此不需要显式的 for 循环。 为什么解法二需要 for 循环
在解法二中递归的逻辑是显式地遍历数组中的元素依次生成子集。具体来说 for 循环从 pos 开始遍历数组 nums表示从当前位置开始选择元素。 对于每个元素 nums[i]将其加入 path然后递归处理下一个元素i 1。 在递归返回后通过 path.pop_back() 回溯恢复现场尝试下一个元素。
这种递归逻辑通过 for 循环显式地遍历元素确保每个元素都有机会被选中并且避免生成重复的子集。 递归和 for 循环的关系 递归的本质是遍历递归确实可以遍历所有元素但遍历的方式可以是隐式的如解法一或显式的如解法二。 是否需要 for 循环取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历如解法一则不需要 for 循环如果需要显式地遍历元素如解法二则需要 for 循环。 两种解法的对比
特性解法一无 for 循环解法二有 for 循环递归逻辑对每个元素做出“选”或“不选”的决策显式遍历元素生成子集是否需要 for 循环否是代码结构更简洁更直观时间复杂度O(2^n)O(2^n) 为什么解法二需要 for 循环
解法二的递归逻辑是通过 for 循环显式地遍历元素确保每个元素都有机会被选中并且避免生成重复的子集。具体来说 显式遍历元素for 循环从 pos 开始遍历数组 nums表示从当前位置开始选择元素。 避免重复子集通过 for 循环从 pos 开始遍历可以避免生成重复的子集。例如如果已经选择了 nums[1]那么后续的子集只能从 nums[2] 开始选择而不能回头选择 nums[0]。 生成所有子集通过 for 循环和递归的结合确保所有可能的子集都被生成。 总结 递归确实可以遍历所有元素但遍历的方式可以是隐式的如解法一或显式的如解法二。 是否需要 for 循环取决于递归的逻辑设计。如果递归的逻辑已经隐含了对所有元素的遍历则不需要 for 循环如果需要显式地遍历元素则需要 for 循环。 解法一和解法二都是正确的只是它们的递归逻辑和实现方式不同。解法一更简洁解法二更直观。
