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

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

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

上一篇描述了针对数组中没有重复元素进行子集的求取过程递归/回溯：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]是重复的集合,则不满足集合的要求。

思考：
同样的递归回溯方式，即每一个元素在是否需要加入到集合中都会有两种状态，存在或者不存在，这里加入的过程中可以对子集进行筛选，如果之前的子集中已经存在有相同的集合，则不需要加入；否则，再将筛选出来的子集加入到最终的集合中。

实现过程如下:
方法一，递归回溯实现

void generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int>> &result,std::set<std::vector<int>> &uniq_result) {if (i >= num.size()) {return;}item.push_back(num[i]);/*当集合中没有当前item时，则加入最终的子集中*/if (uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result);item.pop_back();generate(i + 1, num, item, result, uniq_result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> &num) {std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;//维护一个集合sort(num.begin(), num.end());//对初始序列进行排序result.push_back(item);generate(0, num, item, result, uniq_result);return result;
}

方法二，位运算实现

/*method2*/
std::vector<std::vector<int> > get_subsets2(std::vector<int> &num) {std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;int all_set = 1 << num.size();sort(num.begin(), num.end());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]);}}/*同样使用集合来判断是否需要加入最终的子集中*/if (uniq_result.find(item) == uniq_result.end()) {result.push_back(item);uniq_result.insert(item);}}return result;
}

测试代码如下:
测试[2,1,2,2]

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>/*
Subsets II已知一组数(其中有重复元素)，求这组数可以组成的所有子集。 结果中无重复的子集。
例如: 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]是重复的集合
*/using namespace std;void generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int>> &result,std::set<std::vector<int>> &uniq_result) {if (i >= num.size()) {return;}item.push_back(num[i]);if (uniq_result.find(item) == uniq_result.end()) {result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result);item.pop_back();generate(i + 1, num, item, result, uniq_result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> &num) {std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;sort(num.begin(), num.end());result.push_back(item);generate(0, num, item, result, uniq_result);return result;
}/*method2*/
std::vector<std::vector<int> > get_subsets2(std::vector<int> &num) {std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;int all_set = 1 << num.size();sort(num.begin(), num.end());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]);}}if (uniq_result.find(item) == uniq_result.end()) {result.push_back(item);uniq_result.insert(item);}}return result;
}int main(int argc, char const *argv[])
{std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result;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);}result = get_subsets(num);result2= get_subsets2(num);cout << "method1 " << endl;for (int i = 0;i < result.size(); ++i) {if (result[i].size() == 0) {cout << "[]";}for (int j = 0;j < result[i].size(); ++j) {std::cout << "[" << result[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;
}

输出如下:

4
2 1 2 2
method1 
[]
[1] 
[1] [2] 
[1] [2] [2] 
[1] [2] [2] [2] 
[2] 
[2] [2] 
[2] [2] [2] 
method2 
[]
[1] 
[2] 
[1] [2] 
[2] [2] 
[1] [2] [2] 
[2] [2] [2] 
[1] [2] [2] [2]

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

[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 程序的开发工作，同时提高将用户提供的值编写成字符串，并将字符串传递给其他系统的程序的安全性。支持开发人员自由地表达构造器的行为。