企业官网建设流程全解析

网站建设 国家技术规范,彻底关闭qq顶部小程序入口,电子商务网站建设有什么认识,无货源网店进货app前言回溯算法是基于**深度优先搜索#xff08;DFS#xff09;**的经典算法思想#xff0c;核心是“尝试-回退”#xff0c;通过遍历解空间找到所有符合条件的解。它广泛应用于排列、组合、子集等问题#xff0c;本文将结合LeetCode经典例题#xff0c;用C实现回溯算法DFS**的经典算法思想核心是“尝试-回退”通过遍历解空间找到所有符合条件的解。它广泛应用于排列、组合、子集等问题本文将结合LeetCode经典例题用C实现回溯算法讲解核心思路与实战技巧。一、回溯算法通用框架C回溯的核心是递归函数中完成选择-递归-撤销选择的循环C通用框架模板如下cpp#include vectorusing namespace std;vectorvectorint result; // 存储最终结果void backtrack(/* 路径选择列表其他参数 */) {if (/* 结束条件 */) {result.push_back(/* 当前路径 */);return;}for (/* 遍历选择列表 */) {// 做选择// 递归backtrack(/* 新的路径和选择列表 */);// 撤销选择}}二、经典例题C实现2.1 组合问题LeetCode 77. 组合题目给定 n 和 k 返回 [1,n] 中所有 k 个数的组合。思路用 start 控制选择起点避免重复路径长度等于 k 时保存结果同时剪枝优化。cpp#include vectorusing namespace std;class Solution {private:vectorvectorint res;vectorint path;void backtrack(int n, int k, int start) {if (path.size() k) {res.push_back(path);return;}// 剪枝剩余数字不足时直接退出for (int i start; i n - (k - path.size()) 1; i) {path.push_back(i); // 做选择backtrack(n, k, i 1); // 递归path.pop_back(); // 撤销选择}}public:vectorvectorint combine(int n, int k) {backtrack(n, k, 1);return res;}};2.2 全排列问题LeetCode 46. 全排列题目给定无重复数字的数组 nums 返回所有全排列。思路用 used 数组标记已选元素路径长度等于数组长度时保存结果。cpp#include vectorusing namespace std;class Solution {private:vectorvectorint res;vectorint path;void backtrack(vectorint nums, vectorbool used) {if (path.size() nums.size()) {res.push_back(path);return;}for (int i 0; i nums.size(); i) {if (used[i]) continue; // 跳过已选元素used[i] true; // 做选择path.push_back(nums[i]);backtrack(nums, used); // 递归path.pop_back(); // 撤销选择used[i] false;}}public:vectorvectorint permute(vectorint nums) {vectorbool used(nums.size(), false);backtrack(nums, used);return res;}};2.3 子集问题LeetCode 78. 子集题目给定数组 nums 返回所有可能的子集幂集。思路遍历过程中每一步的路径都是一个子集直接保存用 start 控制选择起点避免重复。cpp#include vectorusing namespace std;class Solution {private:vectorvectorint res;vectorint path;void backtrack(vectorint nums, int start) {res.push_back(path); // 每一步都保存子集for (int i start; i nums.size(); i) {path.push_back(nums[i]); // 做选择backtrack(nums, i 1); // 递归path.pop_back(); // 撤销选择}}public:vectorvectorint subsets(vectorint nums) {backtrack(nums, 0);return res;}};三、回溯算法优化技巧1. 剪枝提前判断当前路径是否无法得到有效解直接跳过分支如组合问题中 i n - (k - path.size()) 1 。2. 状态标记用 bool 数组/哈希表标记已使用元素避免重复选择如全排列的 used 数组。3. 排序去重若数组含重复元素如LeetCode 47. 全排列 II先排序再跳过重复元素避免生成重复解。四、应用场景回溯算法适用于需要穷举所有可能解的场景- 排列/组合/子集类问题- N皇后、数独等棋盘问题- 单词搜索、迷宫路径等搜索问题- 分割回文串、复原IP地址等分割问题。