C++回溯算法中子集问题如何解决
这篇文章主要介绍了C++回溯算法中子集问题如何解决的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇C++回溯算法中子集问题如何解决文章都会有所收获,下面我们一起来看看吧。
一、子集
子集问题与其它问题最大的不同就是:每次递归,不止考虑叶子节点,而是考虑所有节点!
体现在代码上,就是每次递归都先result.push_back(path);
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums,int index){
result.push_back(path);
if(index>=nums.size())
return;
for(int i=index;i<nums.size();i++){
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
二、子集II
本题与上题唯一的区别在于:输入样例有重复数字,但又要求结果不能重复
本题与组合总和II是一个套路,即:横向遍历不可重复,纵向遍历可重复
体现在代码上,就是if(i>index&&nums[i]==nums[i-1]) continue;
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums,int index){
result.push_back(path);
if(index>=nums.size()) return;
for(int i=index;i<nums.size();i++){
if(i>index&&nums[i]==nums[i-1])
continue;
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
backtracking(nums,0);
return result;
}
};
三、递增子序列
这题严格来说并不是子集问题,但是有一点希望和子集II对比一下,就是同一层元素不能重复的问题,这一题因为元素不能排序,所以在判断元素是否重复的问题上,并不能采用类似于上一题的if(i>index&&nums[i]==nums[i-1]) continue;方法,而是应该开辟一个used数组记录每一层元素是否已出现过,其实上一题也能用这种方法,不过上一题没这个必要
还要注意used数组开辟的位置是在backtracking函数内部,意思很明显:used数组只管记录本层元素,至于下一层元素,则要开辟新的ued数组来记录
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums,int index){
if(path.size()>1){
result.push_back(path);
if(index==nums.size()) return;
}
int used[201]={0};//记录本层元素是否重复使用,新的一层都会重新定义
for(int i=index;i<nums.size();i++){
if(used[nums[i]+100]==1||(!path.empty()&&nums[i]<path.back()))
continue;
used[nums[i]+100]=1;
path.push_back(nums[i]);
backtracking(nums,i+1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
相关内容
这些是最新的
热门排行
- THINKPHP5+GatewayWorker+Workerman 开发在线客服系统
- 在手机浏览器网页中点击链接跳转到微信界面的方法
- 尊云网站目录系统 ThinkPHP5网站分类目录程序 v2.2.221011
- CentOS 7安装shadowsock(一键安装脚本)
- AdminTemplate 基于LayUI 2.4.5实现的网站后台管理模板
- 用NW.js(node-webkit)开发多平台的桌面客户端
- PHP生成随机昵称/用户名
- THINKPHP5网站分类目录程序 尊云网站目录系统
- 织梦(DEDECMS)微信支付接口 微信插件
- 基于LayUI开发的 网站后台管理模板 BeginnerAdmin
- 响应式后台网站模板 - AMA.ADMIN
- layuiAdmin后台管理模板 Iframe版
- LayUI 1.0.9 升级 至 LayUI 2.1.4 方法
- 简洁清爽的会员中心模板
- jQuery幸运大转盘抽奖活动代码