当前位置: 首页 > news >正文

回溯法(一)——全排列 全组合 子集问题

全排列问题

  • 数字序列 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题
全排列问题递归树
extern int ans[],l,r,num;//num:方案数
extern bool flag[];
void dfs(int cl){//cl:current left,即为当前递归轮的首元素if(cl == r + 1){//数组已越界,本轮递归结束for(int i=l;i<=r;i++) cout<<ans[i];//从区间头开始扫描并输出cout<<endl;num++;return;}for(int i=l;i<=r;i++){//if(!flag[i]){//剪枝:不允许重复选择已被选择的元素flag[i]=1,ans[cl]=i;dfs(cl + 1);flag[i]=0;//回溯}}
}
全排列问题重复排列剪枝
  • 数组索引 [ l , r ] [l,r] [l,r]​区间内元素的全排列问题

思路:

  1. 让当前的首元素(索引为 c l cl cl)不同,分割成 r r r轮,(首元素相同的称为1轮,共 r r r轮)
    方法:首元素和其之后每个元素交换 (for控制 r r r轮广度)
  2. 每轮中第 [ l + 1 , r ] [l+1,r] [l+1,r]的元素分割出来小区间,令 c l = l + 1 cl=l+1 cl=l+1(对应dfs递归传参),重复步骤1。
    方法:递归控制
extern int a[],l,r,num;//num:方案数
void dfs(int cl){//cl:current left,即为当前递归轮的首元素if(cl == r + 1){//数组已越界,本轮递归结束for(int i = l; i <= r; i++)//从用户输入区间头开始遍历输出cout << a[i];cout << endl;num++;return;}for(int i = cl; i <= r; i++){//从本轮递归区间头开始扫描 i=cl是因为数组本身也算是一种排列方案swap(a[cl], a[i]);//本轮递归区间首元素与其之后每个元素都互换dfs(cl + 1);swap(a[cl], a[i]);//回溯}
}

全组合问题

  • [ l , r ] [l,r] [l,r]区间内组合问题
extern int n, l, r,ans[n];
void dfs(int k, int last) {//k:当前已选元素个数 last:上一轮递归中选择的元素值if (k == n + 1) {//k已越界,输出答案for (int i = 0; i < n; i++) cout<<ans[i]<<' ';cout<<endl;return;}for (int i = last + 1; i <= r; i++) {//从last+1开始是为了选择不会与上一轮递归重复ans[k - 1] = i;dfs(k + 1, i);}
}
int main() {//...dfs(1, l - 1); // 从l-1开始,确保l能被选中//...
}

子集问题

http://www.lryc.cn/news/333579.html

相关文章:

  • 【Pt】马灯贴图绘制过程 04-玻璃脏迹
  • Rust 程序设计语言学习——枚举模式匹配
  • 正则表达式(1)
  • nginx + keepalived 搭建教程
  • React事件和原生事件的执行顺序
  • 为什么在计算查询Q和键K的矩阵乘法时需要转置键矩阵K。示例说明q11,k11代表什么。线性变换矩阵 W_q 用于生成查询,W_k 用于生成键怎么获取的。
  • 剑指Offer题目笔记27(动态规划单序列问题)
  • 撸代码时,有哪些习惯一定要坚持?
  • 【leetcode面试经典150题】17.罗马数字转整数(C++)
  • 前后端开发之——文章分类管理
  • 第12届蓝桥杯省赛 ---- C/C++ C组
  • IVS模型解释
  • 通用开发技能系列:Git
  • 最新怎么订阅OnlyFans上喜欢的博主,详细教程
  • Mysql故障和优化
  • Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理
  • 14届蓝桥杯 C/C++ B组 T7 子串简写 (字符串)
  • Android 系统大致启动流程
  • 【Web】2024红明谷CTF初赛个人wp(2/4)
  • stable-diffusion-webui安装教程
  • 如何魔改 diffusers 中的 pipelines
  • 解放办公室的利器!让证卡打印机轻松应对繁忙工作场景
  • 2012年认证杯SPSSPRO杯数学建模A题(第二阶段)蜘蛛网全过程文档及程序
  • ES学习日记(七)-------Kibana安装和简易使用
  • react 父子组件的渲染机制 | 优化手段
  • elementPlus el-table动态列扩展及二维表格
  • vitepress系列-04-规整sideBar左侧菜单导航
  • golang slice总结
  • MySQL 数据库的优化
  • Redis 的主从复制、哨兵和cluster集群