网站中怎么做视频直播,微页制作网站模板下载,建设模板网站,百度关键词推广怎么做前言#xff1a; 如果你一点也不了解什么叫做回溯算法#xff0c;那么推荐你看看这一篇回溯入门#xff0c;让你快速了解回溯算法的基本原理及框架 递增子序列
给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两… 前言 如果你一点也不了解什么叫做回溯算法那么推荐你看看这一篇回溯入门让你快速了解回溯算法的基本原理及框架 递增子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
来源力扣LeetCode递增子序列 由题意可得下面两点要求
递增的子序列且元素数量大于2子序列与子序列不能相同可使用重复出现的数字
像这种需要依次取元素然后将元素存储起来汇成总集合期间可能还需要回退取不一样集合的题目我们第一个想到的可以使用回溯法那么该如何回溯呢且看下图分析我们使用[ 4,7,6,7 ]举例
回溯收集子集条件 根据题意可以得知我们只要子序列的数量大于等于2就可以回溯终止条件 终止条件就是达到nums.size()单层搜索逻辑 我们由图可以得知虽然序列里面可能有重复的数字但是单层我们不能取相同的数字如果我们取了相同的数字那么必定会存在相同的子集所以我们单层需要去重
单层去重我们这里使用一个标记的容器 unordered_set int use存放已经出现过的数字 代码如下
class Solution {
public:vectorvectorint arr;vectorint _arr;void BackTracking(vectorint nums,int begin){if(_arr.size()2)//只要数据2就存储我们这里不需要return{arr.push_back(_arr);}unordered_setint use;//标记容器for(int ibegin;inums.size();i){//如果是空直接存放然后判断别的关系if((!_arr.empty() _arr.back()nums[i]) || use.find(nums[i])!use.end()){continue;}_arr.push_back(nums[i]);use.insert(nums[i]);BackTracking(nums,i1);//不能重复使用单个数据所以我们需要i1_arr.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {BackTracking(nums,0);return arr;}
};全排列 II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
来源力扣LeetCode全排列 II
本题是全排列的进阶版之前是没有重复元素现在有重复元素我们该如何解决呢 这个题与上一题递增子序列相差不多也是需要单层去重且看下图 相较于之前的收集元素排列我们需要将每个元素都使用到所以我们每次循环开始条件都为0但是为了不使用一个使用过的元素我们需要设置一个标记的数组使用过一个标记一个单层去重是因为同一层使用相同的元素没有意义使用相同元素相当于递归两遍相同数据导致出现相同子集
先排序所有元素标记数组单层去重 代码如下
class Solution {
public:vectorvectorint arr;vectorint _arr;void BackTracking(vectorint nums,vectorbool use){if(_arr.size()nums.size()){arr.push_back(_arr);return;}for(int i0;inums.size();i){//单层去重及判断元素是否使用过if(i0 nums[i]nums[i-1] use[i-1]false){continue;}if(use[i]false){use[i]true;_arr.push_back(nums[i]);BackTracking(nums,use);_arr.pop_back();use[i]false;}}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());//需要排序为去重做准备vectorbool use(nums.size(),false);BackTracking(nums,use);return arr;}
};
