上海公司查询网站烟台做外贸网站

上海公司查询网站,烟台做外贸网站,常见网站架构,建设环境竣工验收网站输入#xff1a;nums [4,4,3,2,1] 输出#xff1a;[[4,4]]注意点此题目的集合是无序的#xff0c;并且要求同一层之间的去重#xff0c;因此和之前有序的同一层去重#xff08;used数组#xff09;不同#xff0c;千万不能混淆。此题还需要对保证输出的组合是有序的nums [4,4,3,2,1]输出[[4,4]]注意点此题目的集合是无序的并且要求同一层之间的去重因此和之前有序的同一层去重used数组不同千万不能混淆。此题还需要对保证输出的组合是有序的因此怎么保证path是有序的。思路无序集合的树层之间去重可以使用unordered_set,记录每一层出现过的元素在for循环之前定义一个for循环是一层因此要在for循环之前定义。并且每一层都单独需要一个unorered_set来记录每一层是否重复因此不需要对unordered_set进行回溯。要保证有序就是要保证正在访问的元素nums[i] path数组中最后一个元素path.back可以表示最后一个元素。但是使用back要保证nums数组不能为空。代码回溯三部曲参数void backtracking(const vectorint nums, int startIndex)终止条件其实也可以不需要终止条件因为递归会一直遍历一直寻找合适的path即走完所有的for循环自动停止。if (path.size() 1) { result.push_back(path); } // 终止条件2如果路径长度等于原数组长度不再继续虽然这种情况很少 if (path.size() nums.size()) return;单层循环逻辑为什么unordered_set创建的位置在for循环之前为什么unordered_set不需要回溯nums.back使用的前提为什么if条件里面的剪枝操作是或的关系为什么是continue而不是break// 关键unordered_set用于记录本层元素是否重复使用 // 注意这个uset的生命周期只在本层递归中每次进入新的递归层都会重新定义 unordered_setint uset; // 遍历从startIndex开始的所有可能选择 for (int i startIndex; i nums.size(); i ) { // 剪枝条件1如果当前元素小于路径最后一个元素跳过不满足递增 // 注意需要先检查path是否为空否则path.back()会出错 // 剪枝条件2如果当前元素在本层已经使用过跳过去重 // 注意这里的去重是针对同一递归层不是针对整个递归树 if ((!path.empty() nums[i] path.back()) || uset.find(nums[i]) ! uset.end()) continue; uset.insert(nums[i]); path.push_back(nums[i]); // 递归从i1开始继续寻找注意是i1不是i因为不能重复使用同一索引的元素 backtracking(nums, i 1); path.pop_back(); // 注意uset不需要撤销因为它在栈上每次递归会重新创建 }整体代码class Solution { private: vectorvectorint result; // 存储所有递增子序列的结果 vectorint path; // 存储当前正在构建的递增子序列 // 回溯函数寻找所有递增子序列 // nums: 输入数组 // startIndex: 当前递归开始选择的起始索引 void backtracking(const vectorint nums, int startIndex) { // 终止条件1当路径长度大于等于2时保存当前递增子序列 // 题目要求子序列长度至少为2 if (path.size() 1) { result.push_back(path); } // 终止条件2如果路径长度等于原数组长度不再继续虽然这种情况很少 if (path.size() nums.size()) return; // 关键unordered_set用于记录本层元素是否重复使用 // 注意这个uset的生命周期只在本层递归中每次进入新的递归层都会重新定义 unordered_setint uset; // 遍历从startIndex开始的所有可能选择 for (int i startIndex; i nums.size(); i ) { // 剪枝条件1如果当前元素小于路径最后一个元素跳过不满足递增 // 注意需要先检查path是否为空否则path.back()会出错 // 剪枝条件2如果当前元素在本层已经使用过跳过去重 // 注意这里的去重是针对同一递归层不是针对整个递归树 if ((!path.empty() nums[i] path.back()) || uset.find(nums[i]) ! uset.end()) continue; uset.insert(nums[i]); path.push_back(nums[i]); // 递归从i1开始继续寻找注意是i1不是i因为不能重复使用同一索引的元素 backtracking(nums, i 1); path.pop_back(); // 注意uset不需要撤销因为它在栈上每次递归会重新创建 } } public: vectorvectorint findSubsequences(vectorint nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };