深圳技术大学oj B : 所有不含逆序对的组合数

Description

数组中可能包含重复的数字, 求由这些数字组成的不重复字符串, 且字符串中不包含逆序对。

Input

有若干组测试数据,(1~20之间) 每一组测试数据第一行输入一个整数 n (0 ≤ n ≤ 20), 代表 n 个数字,接下来的一行输入 n 个整数,分别为 x1, x2 … xn (1 ≤ xi ≤ 9)

Output

输出每组数字组成的不重复字符串,字符串通过逗号隔开

Sample

#0
Input

Copy

4 
3 1 2 3
8
3 4 5 1 6 1 5 5
Output

Copy

,1,12,123,1233,13,133,2,23,233,3,33
,1,11,113,1134,11345,113455,1134555,11345556,1134556,113456,11346,1135,11355,113555,1135556,113556,11356,1136,114,1145,11455,114555,1145556,114556,11456,1146,115,1155,11555,115556,11556,1156,116,13,134,1345,13455,134555,1345556,134556,13456,1346,135,1355,13555,135556,13556,1356,136,14,145,1455,14555,145556,14556,1456,146,15,155,1555,15556,1556,156,16,3,34,345,3455,34555,345556,34556,3456,346,35,355,3555,35556,3556,356,36,4,45,455,4555,45556,4556,456,46,5,55,555,5556,556,56,6

Hint

不选择任何数字时,组成空字符串

回溯求组合数然后排序

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
void DFS(set<string> &ans, vector<int> a, int index, string path)
{//cout << "path=" << path << "OK" << endl;if (index == a.size()){ans.insert(path);return;}//cout << path << " ";DFS(ans, a, index+1, path);DFS(ans, a, index + 1, path + char(a[index] + '0'));}
int main()
{int n;while (cin >> n){vector<int> a;int sd;for (int i = 0; i < n; i++){cin >> sd;a.push_back(sd);}//a.push_back(0);sort(a.begin(), a.end());set<string> s;vector < string>s2;string str="";DFS(s, a, 0, str);for (set<string>::iterator it2 = s.begin(); it2 != s.end(); it2++) {s2.push_back(*it2);}sort(s2.begin(), s2.end());for (vector<string>::iterator it = s2.begin(); it != s2.end(); it++){if (it == s2.begin()) {cout << *it;}else {cout << "," << *it;}}cout << endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/362259.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【仿真建模-anylogic】ViewArea解析

Author&#xff1a;赵志乾 Date&#xff1a;2024-06-27 Declaration&#xff1a;All Right Reserved&#xff01;&#xff01;&#xff01; 1. 应用场景 view area又叫视图区域&#xff0c;其作用是在presentation中标记一块区域&#xff0c;便于动画演示过程中快速切换可视区…

U盘提示格式化怎么搞定?本文有5种方法(内含教程)

U盘提示格式化是一种常见故障&#xff0c;即&#xff1a;当U盘插入电脑后&#xff0c;电脑上弹出对话框&#xff0c;提示该U盘需要格式化才能使用。 接触不良、文件系统损坏、热插拔、感染病毒、芯片损坏等原因都可能导致U盘出现此故障。这时点击“格式化”&#xff0c;大概率会…

Linux通过expect实现免交互

免交互 Here Document 用于将多行字符串直接传递给命令的方式&#xff0c;不需要人为交互命令界面&#xff0c;实现免交互 当使用Here Document操作文件时&#xff0c;需要借助一个文件结束符 EOF&#xff1a;文件结束符 示例 在脚本文件中写入以下内容 <<&#x…

Android 13 修改系统导航默认值

Android 13 原生系统上&#xff0c;设置-系统-手势-系统导航 菜单&#xff0c;可以修改系统导航方式。 手势导航&#xff1a; 三按钮导航&#xff1a; adb 获取当前导航方式&#xff0c;手势导航 是 2 &#xff0c;三按钮导航是 0 。 settings get secure navigation_mode 修…

《Mybatis-Plus》系列文章目录

什么是 MyBatis-Plus&#xff1f; Mybatis-Plus是一个在MyBatis基础上进行增强和扩展的开源Java持久层框架。 Mybatis-Plus&#xff08;简称MP&#xff09;旨在简化开发、提高效率&#xff0c;通过提供一系列便捷的功能和工具&#xff0c;大幅度减少开发人员编写重复代码的时…

RT-Thread Studio实现静态线程

1创建项目 &#xff08;STM32F03ZET6&#xff09; RT-Thread项目与RT-Thread Nano 项目区别 RT-Thread: 完整版&#xff1a;这是RT-Thread的完整形态&#xff0c;适用于资源较丰富的物联网设备。功能&#xff1a;它提供了全面的中间件组件&#xff0c;如文件系统、网络协议栈、…

Go语言之集合类型

个人网站&#xff1a; http://hardyfish.top/ 免费书籍分享&#xff1a; 资料链接&#xff1a;https://url81.ctfile.com/d/57345181-61545511-81795b?p3899 访问密码&#xff1a;3899 免费专栏分享&#xff1a; 资料链接&#xff1a;https://url81.ctfile.com/d/57345181-6…

swiper轮播 loop:true失效解决

数据是写死的时候&#xff0c;能够loop:true是有效的;数据是动态获取的loop:true就会失效。 方法一&#xff1a;在接收到数据后&#xff0c;使用 setTimeout(() > {this.getSwiper(); //生成swiper方法}, 0); 下面是我项目具体使用的参考例子&#xff1a; 方法二&#xff…

问题:ERROR:ldd outputLine:“libprotobuf.so.28 => not found“

想要在Ubuntu上面运行QT打包程序&#xff0c;出现一些问题报错&#xff1a; ERROR:ldd outputLine:"libprotobuf.so.28 > not found" 首先确定一下libprotobuf.so.28的位置&#xff1a; 然后建立一个软链接&#xff1a; ln -s /xxx/xxx/xx.so /usr/lib/xx.so #…

今天不看文章,明天变垃圾(明天收费)-----字节数据分析发展过程中所遭遇的挑战

字节数据分析发展过程中所遭遇的挑战 三个核心议题&#xff1a; 海量数据分析性能&#xff1a;会议指出Spark分析性能不足成为了一个显著问题&#xff0c;尤其是在需要毫秒级响应的业务场景中。实时导入与查询能力&#xff1a;目前Kylin只能以T1的形式提供分析服务&#xff0…

C# 信号量的使用

学习来源&#xff1a;《.net core 底层入门》 第六章第9节&#xff1a;信号量 案例&#xff1a;主线程负责添加数据&#xff0c;子线程负责获取数据 使用SemaphoreSlim&#xff08;轻信号量&#xff09;实现&#xff1a; using System; using System.Collections.Generic; us…

560.滑动窗口最大值

滑动窗口最大值 239. 滑动窗口最大值 - 力扣&#xff08;LeetCode&#xff09; 题目大意&#xff0c;返回每个窗口内的最大值。 思路-优先队列 优先队列&#xff08;堆&#xff09;&#xff0c;其中的大根堆可以实时维护一系列元素中的最大值。 每当我们向右移动窗口时&#…

vue3+ts <script setup lang=“ts“> element-plus的el-date-picker设置默认日期

效果图&#xff08;单个日期&#xff09;&#xff1a; utils.ts&#xff1a; /*** 格式化时间戳* param {number} timestamp 时间戳* param {string} format 格式* returns {string}*/ export const formatTimeStamp (timestamp: number, format: string) > {if (!timesta…

深入解析Java和Go语言中String与byte数组的转换原理

1.Java String与byte[]互相转换存在的问题 java中&#xff0c;按照byte[] 》string 》byte[]的流程转换后&#xff0c;byte数据与最初的byte不一致。 多说无益&#xff0c;上代码&#xff0c;本地macos机器执行&#xff0c;统一使用的UTF-8编码。 import java.nio.charset.S…

Linux-笔记 嵌入式gdb远程调试

目录 前言 实现 1、内核配置 2、GDB移植 3、准备调试程序 4、开始调试 前言 gdb调试器是基于命令行的GNU项目调试器&#xff0c;通过gdb工具我们可以实现许多调试手段&#xff0c;同时gdb支持多种语言&#xff0c;兼容性很强。 在桌面 Linux 系统&#xff08;如 Ubuntu、Cent…

【Java】微博系统设计:怎么应对热点事件的突发访问压力?

一、问题解析 微博&#xff08;microblog&#xff09;是一种允许用户即时更新简短文本&#xff08;比如140个字符&#xff09;&#xff0c;并可以公开发布的微型博客形式。今天我们就来开发一个面向全球用户、可以支持10亿级用户体量的微博系统&#xff0c;系统名称为“Weitte…

2024连云港等保测评机构看这里!

2024连云港等保测评机构看这里&#xff01; 目前连云港暂未有具有等保资质的机构。因此连云港企业可以就近选择江苏省内等保测评机构&#xff0c;或者在网上寻找合适的机构。 连云港城市简单介绍 连云港——江苏省辖地级市&#xff0c;地处沿海中部&#xff0c;东濒黄海&…

访问网站时IP被屏蔽是什么原因?

在互联网使用中&#xff0c;有时我们可能会遇到访问某个网站时IP地址被屏蔽的情况。IP地址被网站屏蔽是一个相对常见的现象&#xff0c;而导致这种情况的原因多种多样&#xff0c;包括恶意行为、违规访问等。本文将解释IP地址被网站屏蔽的常见原因&#xff0c;同时&#xff0c;…

编译VTK静态库

编译VTK静态库遇到问题 vtkCommonCore-9.3d.lib(vtkSMPToolsAPI.obj) : error LNK2019: unresolved external symbol "public: bool __cdecl vtk::detail::smp::vtkSMPToolsImpl<1>::IsParallelScope(void)" (?IsParallelScope?$vtkSMPToolsImpl$00smpdetai…

JVM专题七:JVM垃圾回收机制

JVM专题六&#xff1a;JVM的内存模型中&#xff0c;我们介绍了JVM内存主要分哪些区域&#xff0c;这些区域分别是干什么的&#xff0c;同时也举了个例子&#xff0c;在运行过程种各个区域数据是怎样流转的。细心的小伙伴可能发现一个问题&#xff0c;在介绍完方法弹栈以后就没有…