非递减子序列

📅 2026/7/1 2:41:02 👁️ 次浏览

压入结果的条件是path.size()2回溯过程结束的条件是移动到了边上startIndexnum.size()在树中非递减序列要求压入的元素必须比之前压入的大if(path.empty()||nums[i]path.back())问题如果给出的数组包含重复元素那么答案的集合中就会包含重复的数组那我标记该位置的元素已经用过了如何if(used[i]false(path.empty()||nums[i]path.back())) { path.push_back(nums[i]); used[i]true; backtrack(nums,i1,used); path.pop_back(); used[i]false; }这样也是不行的原因在于数组不同下标处的元素可能相等这样只是标记了一个位置的该元素但是如果该位置后面的元素和已经遍历过的元素有相同的也会导致结果集中存在一样的数组。所以重点不是对下标记录而是对这个元素本身的值进行记录。使用哈希容器unorder_setint usedThisLevalfor(int istartIndex;inums.size();i){ if(usedThisLeval.contains(nums[i])){ continue; } if(path.empty()||nums[i]path.back()) { path.push_back(nums[i]); usedThisLeval.insert(nums[i]); backtrack(nums,i1); path.pop_back(); } }但是似乎很慢原始思路解法代码class Solution { public: vectorintpath; setvectorint res; void backtrack(vectorintnums, int startIndex){ if(path.size()2){ res.insert(path); } if(startIndexnums.size()){ return; } for(int istartIndex;inums.size();i){ if(path.empty()||nums[i]path.back()) {path.push_back(nums[i]); backtrack(nums,i1); path.pop_back();} } } vectorvectorint findSubsequences(vectorint nums) { path.clear(); res.clear(); backtrack(nums,0); return vectorvectorint(res.begin(),res.end()); } };全排列题目描述给定一个不含重复数字的数组返回其所有可能的全排列。看到题目第一眼感觉这道题和之前做过的组合问题很相似。组合问题在n个数中找K个数的组合。复用后发现不同N个数的组合在组合问题中是这种情况在回溯的这颗树中在移动startIndex的过程中之前的数就不会考虑进来了但是排列问题需要考虑进来。解决办法是vector used标记状态class Solution { public: vectorintpath; vectorvectorint res; void backtrack(vectorintnums, vectorboolused){ if(path.size()nums.size()){ res.push_back(path); return; } for(int i0;inums.size();i){ if(used[i]true){ continue;//跳出本次循环 } used[i]true; {path.push_back(nums[i]); backtrack(nums,used); path.pop_back(); used[i]false;} } } vectorvectorint permute(vectorint nums) { path.clear(); res.clear(); vectorboolused(nums.size(),false); backtrack(nums,used); return res; } };全排列2问题理解数组中出现了重复元素使用暴力set去重但是似乎是一种很慢的方法相当于每次插入都要遍历一次所有组合。代码class Solution { public: vectorintpath; vectorvectorint res; void backtrack(vectorintnums, vectorboolused){ if(path.size()nums.size()){ res.push_back(path); return; } for(int i0;inums.size();i){ if(i0nums[i]nums[i-1]used[i-1]true){ continue;//跳出本次循环 } if(used[i]false){ used[i]true; path.push_back(nums[i]); backtrack(nums,used); path.pop_back(); used[i]false; } } } vectorvectorint permuteUnique(vectorint nums) { path.clear(); res.clear(); sort(nums.begin(),nums.end()); vectorboolused(nums.size(),false); backtrack(nums,used); return res; } };

相关新闻