当前位置：首页 > 编程日记 > 正文

递归/回溯：subsets求子集

编程日记 2024-04-20 11:30:00

前言
回溯法又称为试探法，但当探索到某一步时，发现原先选择达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

已知一组数(其中无重复元素)，求这组数可以组成的所有子集。结果中不可有无重复的子集。
例如: nums[] = [1, 2, 3]
结果为: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

以上的初始数组集合中，每一个数在产生的子集中都有两种可能：存在、不存在
那么最终的子集个数就为2^n,(n为初始数组的大小)

如果仅仅生成[1],[1,2],[1,2,3]这样的集合，那么该如何实现呢？
过程如下：
方法一：使用普通的循环

std::vector<std::vector<int> > get_subsets2(std::vector<int> num) {std::vector<std::vector<int> > result; //存放最终的结果std::vector<int> item; //存放临时数组for (int i = 0;i < num.size(); ++i) {item.push_back(num[i]);result.push_back(item);}return result;
}

方法二：使用回溯的递归实现

void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {//结束条件即为遍历到最后一个元素return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result); //每一次对下标++
}std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;generate(0,num,item,result);return result;
}

那么接下来需要生成最终的2^3个数的子集
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

方法一：
回溯法生成子集，因为针对每一个元素，都只有两种可能性，存在于子集或者不存在于子集之中，那么针对以上两种可能性，都可以选择递归进行后续元素的放入，每种元素同样有两种可能性，存在或者不存在；

例如 [1,2,3…]
针对元素1，有两种可能性:
item = [1],后续继续按照两种可能进行下一个元素的存放: item = [1,2],item = [1] …
item = [],后续继续按照两种可能进行下一个元素的存放: item = [2],item = [] …

这个过程使用递归实现如下:

void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return;}/*两种可能：1. 放入当前元素2. 不放入当前元素*/item.push_back(num[i]);  //放入当前元素result.push_back(item);generate2(i+1, num, item, result); item.pop_back();// 不放入当前元素generate2(i+1, num, item, result);
}
/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item); //空元素提前放入generate2(0,num,item,result);return result;
}

方法二：
使用位运算符进行运算，过程如下：
因为针对每一种元素都有两种可能，存在或者不存在；那么这个状态可以用0或者1代替；
若一个集合有三个元素A, B, C，则3个元素有2^3 = 8 种组成集合的方式，用0-7表示这些集合。即从000-111这个二进制范围代替，每一位代表对应元素的存在状态，0代表该元素不放入集合，1代表该元素放入了集合，总共有2^n种状态。

构造A元素为100 = 4且1<<2 = 4 ，B元素为010 = 2且 1 << 1 = 2, C元素为001 = 1 且1 << 0 = 1，构造如下表格(表格中的按位与的结果并不是真正的与之后的数值，而是代表对应元素存在与否的真值):

集合	整数	A是否出现	B是否出现	C是否出现
{}	000=0	1 << 2 & 000 = 0	1 << 1 & 000 = 0	1 << 0 & 000 = 0
{C}	001=1	1 << 2 & 001 = 0	1 << 1 & 001 = 0	1 << 0 & 001 = 1
{B}	010=2	1 << 2 & 010 = 0	1 << 1 & 010 = 1	1 << 0 & 010 = 0
{B,C}	011=3	1 << 2 & 011 = 0	1 << 1 & 011 = 1	1 << 0 & 011 = 1
{A}	100=4	1 << 2 & 100 = 1	1 << 1 & 100 = 0	1 << 0 & 100 = 0
{A,C}	101=5	1 << 2 & 101 = 1	1 << 1 & 101 = 0	1 << 0 & 101 = 1
{A,B}	110=6	1 << 2 & 110 = 1	1 << 1 & 110 = 1	1 << 0 & 110 = 0
{A,B,C}	111=7	1 << 2 & 111 = 1	1 << 1 & 111=1	1 << 0 & 111 = 1

实现过程如下:

/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){std::vector<std::vector<int> > result;int all_set = 1 << num.size();for (int i = 0;i < all_set; ++i) {//遍历所有可能的结果std::vector<int> item;for (int j = 0;j < num.size(); ++j) {if (i & (1 << j)) { //通过一一比对，核对最终j下标代表的元素是否存在item.push_back(num[j]);}}result.push_back(item);}return result;
}

测试代码如下:

#include <iostream>
#include <vector>
#include <algorithm>/*
Subsets已知一组数(其中无重复元素)，求这组数可以组成的所有子集。 结果中不可有无重复的子集。
例如: nums[] = [1, 2, 3]
结果为: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
*/using namespace std;
void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result);
} std::vector<std::vector<int> > get_subsets2(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);for (int i = 0;i < num.size(); ++i) {item.push_back(num[i]);result.push_back(item);}return result;
}void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) {if (i >= num.size()) {return;}item.push_back(num[i]);result.push_back(item);generate2(i+1, num, item, result);item.pop_back();generate2(i+1, num, item, result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) {std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);generate2(0,num,item,result);return result;
}/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){std::vector<std::vector<int> > result;int all_set = 1 << num.size();for (int i = 0;i < all_set; ++i) {std::vector<int> item;for (int j = 0;j < num.size(); ++j) {if (i & (1 << j)) {item.push_back(num[j]);}}result.push_back(item);}return result;
}	int main(int argc, char const *argv[])
{std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result1;std::vector<std::vector<int>> result2;int tmp;int N;std::cin >> N;for (int i  = 0;i < N; ++i) {std::cin >> tmp;num.push_back(tmp);}result1= get_subsets(num);result2= generate3(num);cout << "method1 " << endl;for (int i = 0;i < result1.size(); ++i) {if (result1[i].size() == 0) {cout << "[]";}for (int j = 0;j < result1[i].size(); ++j) {std::cout << "[" << result1[i][j] << "] ";}std::cout << std::endl;}cout << "method2 " << endl;for (int i = 0;i < result2.size(); ++i) {if (result2[i].size() == 0) {cout << "[]";}for (int j = 0;j < result2[i].size(); ++j) {std::cout << "[" << result2[i][j] << "] ";}std::cout << std::endl;}return 0;
}

输出如下:

3
1 2 3
method1 
[]
[1] 
[1] [2] 
[1] [2] [3] 
[1] [3] 
[2] 
[2] [3] 
[3] 
method2 
[]
[1] 
[2] 
[1] [2] 
[3] 
[1] [3] 
[2] [3] 
[1] [2] [3]

可以看到递归回溯遍历的结果和位运算遍历到的结果输出顺序上是有差异的，递归回溯需要一直遍历到最终的尾元素，而位运算则是遍历过程中一个一个添加。

https://www.dkcj.cn/info/4957.html

C++ stl vector介绍

转自： STL vector用法介绍介绍这篇文章的目的是为了介绍std::vector，如何恰当地使用它们的成员函数等操作。本文中还讨论了条件函数和函数指针在迭代算法中使用，如在remove_if()和for_each()中的使用。通过阅读这篇文章读者应该能够有效地使…

编程日记2024/04/20 11:00:00

Linux服务器部署ssl证书教程,linux服务器在wdcp面板安装ssl证书教程

不少站长如今越来越在意站内数据传输的安全性，想着把自己建设的网站加密传输，许多站长都需要安装ssl证书，且很多站长都在找寻centos系统服务器linux服务器或者是wdcp面板怎么安装ssl证书，网上找了下没有完整步骤教程，所…

编程日记2024/04/20 10:30:00

设备节点注册和操作方法连接

今天把驱动程序乱七八糟的看了一通，简单总结一下。一个完整的驱动，需要提供如下的东西， 第一，用户空间/dev下面的设备节点。当然，如果该设备仅仅是内核的使用，例如I2C，则不需要在/dev下面建立…

编程日记2024/04/20 10:00:00

maven（一基本操作命令标签）

原来一直没有使用maven 小公司，只是听说过这个东西，我没事就喜欢去学习一些新东西。maven学了几次，但是没有用上所以最后还是忘记了，或者说不知道怎么使用maven，一年半以前公司改革 ，招了一个技术大牛…

编程日记2024/04/20 09:30:00

递归/回溯：Subsets II求子集（有重复元素）

上一篇描述了针对数组中没有重复元素进行子集的求取过程递归/回溯：subsets求子集但是当出现如下数组时： 例如: nums[] [2, 1, 2, 2] 结果为: [[], [1], [1,2], [1,2,2], [1,2,2,2], [2], [2,2], [2,2,2]] 注意: [2,1,2]与[1,2,2]是重复的集合,则不满足…

编程日记2024/04/20 09:00:00

[WP]使用ApacheCordova开发HTML5-WindowsPhone应用程序

下载代码示例这篇文章介绍 Apache 科尔多瓦，创建使用 HTML5 和 JavaScript，跨平台移动应用程序的框架，并显示了如何使用它为 Windows Phone 开发应用程序。 Windows Phone 和其本机开发平台允许您轻松地创建美丽地铁样式的应用程序。最近诺…

编程日记2024/04/20 08:30:00

linux 不能运行程序代码,linux-无法在Ubuntu上运行我自己的OpenGL 3程序

我正在尝试OpenGL 2.x和3.x教程.程序进行编译和链接,然后在看似无害的行上进行段错误处理,例如glGenBuffers (1, &m_buffer);我的main()以glewInit和glutInit开头. OpenGL 1程序可以编译并正常运行,这似乎是由glew包装的新功能.一个教程说,在尝试任何其他操作之前,我应该先…

编程日记2024/04/20 08:00:00

Cocos2d-x Eclipse下程序运行产生错误Effect initCheck() returned -1

错误大致显示如下信息：04-14 07:39:18.325: E/AudioEffect(20584): set(): AudioFlinger could not create effect, status: -104-14 07:39:18.325: E/libOpenSLES(20584): Effect initCheck() returned -104-14 07:39:18.325: E/libOpenSLES(20584): Environmental…

编程日记2024/04/20 07:30:00

H2：开源内存数据库引擎

本资源由伯乐在线 - 刘立华整理H2是一个开源的内存数据库。Java编写、快速、小巧（1.5MB jar包）还提供了Web控制台管理数据库内容。主要功能非常快速的数据库引擎。开源。Java编写。支持标准SQL、JDBC API。支持嵌入式模式、服务器模式和集群。强大的…

编程日记2024/04/20 07:00:00

递归/回溯：Combination Sum II数组之和

问题如下： 已知一组数(其中有重复元素)，求这组数可以组成的所有子集中，子集中的各个元素和为整数target的子集，结果中无重复的子集。例如: nums[] [10, 1, 2, 7, 6, 1, 5]， target 8 结果为: [[1, 7], [1, 2, 5], …

编程日记2024/04/20 06:30:00

如何在SharePoint2010中添加Deep Zoom Image

如何在SharePoint2010中添加Deep Zoom Image 应用范围 SharePoint 2010 Foundation；SharePoint 2010 Standard；SharePoint 2010 Enterprise所需材料 1. SeaDragon Ajax Viewer Web部件（点击此处下载）2. Deep Zoom Image Composer&…

编程日记2024/04/20 06:00:00

linux 读取磁盘扇区,linux 下检查硬盘坏道/扇区

文章摘自：Linux检测硬盘坏道Linux检测硬盘坏道badblocks功能说明：检查磁盘装置中损坏的区块。语法：badblocks [-svw][-b ][-o ][磁盘装置][磁盘区块数][启始区块]补充说明：执行指令时须指定所要检查的磁盘装置，及此装置…

编程日记2024/04/20 05:30:00

Pjax是什么以及为什么推荐大家用

什么是pjax? 现在很多网站( facebook, twitter) 都支持这样的一种浏览方式， 当你点击一个站内的链接的时候， 不是做页面跳转， 而是只是站内页面刷新。这样的用户体验， 比起整个页面都闪一下来说， 好很多。其中有一…

编程日记2024/04/20 05:00:00

Scrapy框架CrawlSpider类爬虫实例

CrawlSpider类爬虫中： rules用于定义提取URl地址规则，元祖数据有顺序 #LinkExtractor 连接提取器，提取url地址 #callback 提取出来的url地址的response会交给callback处理 #follow 当前url地址的响应是否重新经过rules进行提取url地址 cf.py具…

编程日记2024/04/20 04:30:00

递归/回溯：Generate Parentheses生成合法括号

已知n组括号，开发一个程序，生成这n组括号所有的合法的组合可能。例如:n 3 结果为: ["((()))", “(()())”, “(())()”, “()(())”, “()()()”] 首先思考如何生成所有的括号组合的可能性，即例如2组括号，总共4个符号…

编程日记2024/04/20 04:00:00

利用“哨兵”“实现双链表

利用“哨兵”“实现双链表下面的代码用一个”哨兵“实现双链表，感觉很简洁，中间也有点绕，暂时实现，供学习之用 static Node list_handle {&list_handle,&list_handle, };bool addNode(Node* node) {if (node NULL){re…

编程日记2024/04/20 03:30:00

suse linux显示乱码,open suse11.4中文乱码问题

winland0704 于 2011-04-07 00:56:10发表:不是乱码，而是字符编码标准不一样。windows的文本使用GBK，国标码。Linux使用Unicode编码。解决参看：hi.baidu.com/winland0704/blog/item/c58008512cc843c9b645aef1.html四、其他的一些问题3、文本编…

编程日记2024/04/20 03:00:00

软件破解系列之OD中断方法

OD中断方法浅探 Ollydbg是一个新的32位的汇编层调试软件。适应于windows98、me、2000、xp和2003操作系统。由于他具有图形窗口界面，所以操作方便、直观，是cracker的好工具。由于Ollydbg没有了TRW2000的万能断点，所以许多的新手感觉到用Ollyd…

编程日记2024/04/20 02:30:00

MongoDB系列：二、MongoDB常用操作练习

最近在自学MongoDB，在此记录一下，当做学习笔记了（不断更新中）！！ 一、背景 MongoDB 是一个基于分布式文件存储的数据库。由 C 语言编写。旨在为 WEB 应用提供可扩展的高性能数据存储解决方案。它是一个介于关…

编程日记2024/04/20 02:00:00

递归/回溯：八皇后问题N-Queens

N皇后问题是计算机科学中最为经典的问题之一，该问题可追溯到1848年，由国际西洋棋棋手马克斯贝瑟尔于提出了8皇后问题。将N个皇后放摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎样的? 8…

编程日记2024/04/20 01:30:00

KS103超声波测距模块

max232：电平转换芯片，将电脑的RS-232标准串口（高12V，低-12V）转换为（高5V，低0V）。电脑串口（RS -232） > 单片机串口（TTL串口） SIPEX…

编程日记2024/04/20 01:00:00

linux 硬盘操作,linux常用disk磁盘操作命令

编程日记2024/04/20 00:30:00

在Spring中采用声明式方法对Hibernate和JDBC进行统一的事务配置（AOP）

<?xml version"1.0" encoding"UTF-8"?><beans xmlns"http://www.springframework.org/schema/beans" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance" xmlns:aop"http://www.springframework.…

编程日记2024/04/20 00:00:00

Leetcode 213.大家劫舍II

打家劫舍II 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房…

编程日记2024/04/19 23:30:00

替代Druid，HakariCP 为什么这么快？

这次源码探究，真的感觉看到了无数个小细节，无数个小优化，积少成多。平时开发过程中，一些小的细节也一定要“扣”。

编程日记2024/04/19 23:00:02

递归/分治：归并排序

前言分治算法: 将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解后进行合并，就可得到原问题的解。步骤如下: 分解，将要解决的问题划分成若干规模较小的同类问题;求解，…

编程日记2024/04/19 23:00:00

Java中volatile 的使用场景有哪些？

volatile是一种轻量级的同步机制，它能保证共享变量的可见性，同时禁止重排序保证了操作的有序性，但是它无法保证原子性。所以使用volatilevolatile。

编程日记2024/04/19 22:30:05

JDK22 正式发布了！

Java 22 除了推出了新的增强功能和特性，也获得 Java Management Service (JMS) 的支持，这是一项新的 Oracle 云基础设施远程软件服务(Oracle Cloud Infrastructure, OCI) 原生服务，提供统一的控制台和仪表盘，帮助企业管理本地或云端的 Java 运行时和应用。使包含运行时计算值的字符串更容易表达，简化 Java 程序的开发工作，同时提高将用户提供的值编写成字符串，并将字符串传递给其他系统的程序的安全性。支持开发人员自由地表达构造器的行为。

编程日记2024/04/19 22:30:05

Jackson 用起来！

你可以创建自定义序列化器和反序列化器以自定义特定字段或类的序列化和反序列化行为。为此，请创建一个实现或接口的类，并在需要自定义的字段或类上使用和注解。@Override// ...其他代码...优势性能优异：Jackson在序列化和反序列化过程中表现出优秀的性能，通常比其他Java JSON库更快。灵活性：通过注解、自定义序列化器/反序列化器等功能，Jackson提供了丰富的配置选项，允许你根据需求灵活地处理JSON数据。易于使用：Jackson的API设计简洁明了，易于学习和使用。

编程日记2024/04/19 22:30:05

Swift中的问号?和感叹号!

Swift语言使用var定义变量，但和别的语言不同，Swift里不会自动给变量赋初始值，也就是说变量不会有默认值，所以要求使用变量之前必须要对其初始化。如果在使用变量之前不进行初始化就会报错： var stringValue : String …

编程日记2024/04/19 22:30:00

相关文章：