企业官网建设流程全解析

做网站为什么每年都要续费,个人主页怎么找,做网站赚钱吗 怎么赚,电商网站建设综述问题要求#xff1a;给定一个候选数集 (candidates) 和一个目标数 (target)#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 关键约束#xff1a;1. candidates 中的每个数字在每个组合中只能使用一次。2. 解集不能包含重复的组合。一句话就是#xff1a…问题要求给定一个候选数集 (candidates) 和一个目标数 (target)找出 candidates 中所有可以使数字和为 target 的组合。关键约束1. candidates 中的每个数字在每个组合中只能使用一次。2. 解集不能包含重复的组合。一句话就是有重复的元素怎么得到不重复的集合比如{111 2}target 3 问题的难点在于最终的集合是{1 2}{1 1 1}而在以往的算法答案是{1 2} {1 2}{1 2}为什么有三个{1 2}是因为有三个{1 1 1} 因此难点在于怎么去重。分析首先我们已知回溯算法可以抽象为一颗树分为横向和纵向横向表示同一层的元素比如{1 2} {1 2}{1 2}这是因为三个1都在第一层分别选择了三次纵向表示同一树枝的元素比如{1 1 1}表示三个1分别在三层他们在同一个集合三次递归选中了1。通过以上的分析可知我们想要得到不重复的集合就是要在去重同一层重复的元素。思路首先肯定是要对元素进行排序一方面是为了剪枝一方面方便处理重复的元素。去重逻辑 (关键)当满足以下三个条件时跳过当前元素以避免重复组合1. i 0确保 i-1 索引有效。2. candidates[i] candidates[i - 1]当前元素与前一个元素相同。3. used[i - 1] false前一个相同的元素在搜索中没有被使用这表明二者是同一层的元素如果used[i - 1] true表明二者是同一个树枝上的元素所以这个条件十分重要用来确定是同一层还是同一树枝。这表示我们已经处理过以 candidates[i-1] 开头的组合现在为了避免重复需要跳过以 candidates[i] 开头的相同组合。if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { continue; }代码#include iostream #include vector #include string #include algorithm using namespace std; // LeetCode 问题组合总和 II // 问题要求给定一个候选数集 (candidates) 和一个目标数 (target)找出 candidates 中所有可以使数字和为 target 的组合。 // 关键约束 // 1. candidates 中的每个数字在每个组合中只能使用一次。 // 2. 解集不能包含重复的组合。 class Solution { private: vectorint path; // 存储当前正在构建的组合路径 vectorvectorint result; // 存储所有符合条件的最终组合 /** * brief 核心回溯函数 * param candidates 候选数组 * param targetSum 目标和 * param sum 当前路径的和 * param startIndex 搜索的起始索引用于防止元素重复使用 * param used 标记数组用于在处理重复数时去重 */ void backtracking(const vectorint candidates, int targetSum, int sum, int startIndex, vectorbool used) { // 终止条件如果当前和等于目标值说明找到了一个有效组合 if (sum targetSum) { result.push_back(path); // 将当前路径添加到结果集中 return; } // 遍历候选数组 // 剪枝优化i candidates.size() sum candidates[i] targetSum // 如果当前元素加上当前和已经超过了目标值那么后续更大的元素也必然超过因此可以提前终止循环。 for (int i startIndex; i candidates.size() sum candidates[i] targetSum; i) { // 去重逻辑 (关键) // 当满足以下三个条件时跳过当前元素以避免重复组合 // 1. i 0确保 i-1 索引有效。 // 2. candidates[i] candidates[i - 1]当前元素与前一个元素相同。 // 3. used[i - 1] false前一个相同的元素在搜索中没有被使用这表明二者是同一层的元素如果used[i - 1] true表明二者是同一个树枝上的元素 // 这表示我们已经处理过以 candidates[i-1] 开头的组合现在为了避免重复 // 需要跳过以 candidates[i] 开头的相同组合。 if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { continue; } // --- 做出选择 --- path.push_back(candidates[i]); // 将当前元素加入路径 used[i] true; // 标记当前元素已使用 sum candidates[i]; // 更新当前和 // --- 递归进入下一层 --- // 递归调用 backtracking从下一个索引 i 1 开始搜索确保每个数字只用一次。 backtracking(candidates, targetSum, sum, i 1, used); // --- 撤销选择 (回溯) --- sum - candidates[i]; // 恢复当前和 used[i] false; // 取消标记 path.pop_back(); // 将当前元素移出路径为同层其他选择让路 } } public: /** * brief 主函数用于寻找所有和为 target 的组合 * param candidates 候选数组 * param target 目标和 * return 返回所有符合条件的组合 */ vectorvectorint combinationSum2(vectorint candidates, int target) { path.clear(); // 清空上一次的路径 result.clear(); // 清空上一次的结果 // 初始化 used 数组大小与 candidates 相同全部置为 false (未使用) vectorbool used(candidates.size(), false); // 排序是去重逻辑的前提。排序后所有相同的元素都会相邻排列。 sort(candidates.begin(), candidates.end()); // 从索引 0 开始进行回溯搜索 backtracking(candidates, target, 0, 0, used); return result; // 返回最终结果 } }; // --- 主测试函数 --- int main() { Solution S; // 创建 Solution 类的实例 // 测试用例一个包含重复数字的数组 vectorint candidates {10, 1, 2, 7, 6, 1, 5, 2, 2, 2}; int target 8; // 调用函数获取所有符合条件的组合 vectorvectorint res S.combinationSum2(candidates, target); // --- 输出结果 --- cout 所有和为 target 的组合 endl; for (auto row : res) { // 遍历每一个组合 (row) for (auto col : row) { // 遍历组合中的每一个数字 (col) cout col ; } cout endl; // 每个组合输出后换行 } return 0; // 程序正常退出 }