null - 程序员宅基地

Sum It Up POJ 1564 HDU 杭电1258【DFS】_problem description given a specified total t and -程序员宅基地

Problem Description

Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four different sums that equal 4: 4,3+1,2+2, and 2+1+1.(A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

Input

The input will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1,...,xn. If n=0 it signals the end of the input; otherwise, t will be a positive integer less than 1000, n will be an integer between 1 and 12(inclusive), and x1,...,xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.

Output

For each test case, first output a line containing 'Sums of', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line 'NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distince; the same sum connot appear twice.

Sample Input

  
  
   
    
   
   4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0

Sample Output

  
  
   
    
   
   Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25

#include<stdio.h>
#include<string.h>
int sum,n;
int a[1010];
int res[1010]={10000};
bool vis[1010];
int j;
bool flag=0;
void DFS(int m,int cnt)
{
	int i;//这个i DFS时要用上，且作用很大，一定得放在里面，我一开始定义了个全局变量，找了快两小时 才找到 
	if(m==0)
	{
		flag=1;
		for(j=1;j<cnt-1;++j)
			printf("%d+",res[j]);
		printf("%d\n",res[j]);
		return ;
	}
	for(i=1;i<=n;++i)
	{
		//
		if(!vis[i]&&m-a[i]>=0&&a[i]<=res[cnt-1])
		{
			vis[i]=1;
			res[cnt]=a[i];                                             
			DFS(m-a[i],cnt+1);
			vis[i]=0;
			while(a[i]==a[i+1]&&i<=n) ++i;
		}
	}

}
int main()
{
	int i;
	while(~scanf("%d%d",&sum,&n),sum+n)
	{
		flag=0;
		for(i=1;i<=n;++i)
		{
			scanf("%d",a+i);
		}
		printf("Sums of %d:\n",sum); 
		memset(vis,0,sizeof(vis));
		DFS(sum,1);
		if(!flag)printf("NONE\n");
	}
	return 0;
}

本文链接：https://blog.csdn.net/yuzhiwei1995/article/details/47607909

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

wen zi gun dong-程序员宅基地

文章浏览阅读89次。html<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><hea..._"intid[i] = setinterval(function(){ if(_this.find(\".123\").height()<=_this"

C语言动态函数调用_c语言动态调用函数-程序员宅基地

文章浏览阅读2.6k次。在远程调用中，服务器在收到请求后，需要通过查符号的手段，获取函数指针，然后调用客户端请求的函数。然而，不同函数参数个数、类型皆不相同，函数指针在定义时就需要明确类型，因此，没有一种定义，可以满足所有函数的调用。_c语言动态调用函数

Android程序员：为了跳槽刷完1307页的面试真题，没想到老板直接给我升职了-程序员宅基地

文章浏览阅读744次，点赞23次，收藏18次。最后为了帮助大家深刻理解Android相关知识点的原理以及面试相关知识，这里放上相关的我搜集整理的14套腾讯、字节跳动、阿里、百度等2021最新面试真题解析，我把技术点整理成了视频和PDF（实际上比预期多花了不少精力），包知识脉络 + 诸多细节。网上学习 Android的资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。本文已被CODING开源项目：《Android学习笔记总结+移动架构视频+大厂面试真题+项目实战源码》收录。

代理模式的简单理解_代理模式作用简洁-程序员宅基地

文章浏览阅读134次。简介代理模式是程序员前辈们总结出来的一种设计模式，它出现的作用是降低程序的耦合度，更利于程序的扩展，它的要求：① 必须有一个接口（抽象主题角色）② 有一个实现类实现这个接口（真实主题角色）③ 然后再来一个实现类也去实现接口（代理主题角色）④ 第二个实现类中持有第一个实现类的对象作为属性⑤ 第二个实现类中也要重写接口的所有抽象方法，但是在重写方法的时候，调用第一个实现类对象的对应方法，..._代理模式作用简洁

OPENCV2.4.7+VS2010+海康威视摄像头_sadp_lib-程序员宅基地

文章浏览阅读1k次。准备：VS2010,OpenCV2.4.7,海康威视网络PTZ摄像头，Win10操作系统。一．摄像头的安装1.按照说明书安装好摄像头，用网线连接在电脑上，配置电脑IP或者摄像头IP，保证摄像头和电脑在同一个网段，这时摄像头会提醒成功连接网络。2.从海康威视官网上下载SADP并安装（这个版本的SADP我下载下来以后装上了却用不了，后来我就下了比这个低一个版本的，可以使用），按照说明书在S..._sadp_lib

Web前端开发快速学习，0基础前端开发，web前端开发工程师找工作，web开发学什么-程序员宅基地

文章浏览阅读604次，点赞10次，收藏8次。自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。深知大多数前端工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！因此收集整理了一份《2024年Web前端开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

随便推点

尚硅谷最新版JavaScript基础全套教程完整版（p48-p65）_尚硅谷javascript新书大纲-程序员宅基地

文章浏览阅读237次。尚硅谷最新版JavaScript基础全套教程完整版(140集实战教学,JS从入门到精通)一、基本数据类型和引用数据类型1.基本数据类型-string 、 number 、 Boolean 、null 、undefined2.引用数据类型-object3.区别-JS中的变量都是保存到栈内存中的，基本数据类型的值直接在栈内存中存储，值与值之间是独立存在的，修改一个变量不会影响另外一个变量。-引用数据类型（对象）是保存到堆内存中的，每创建一个新的对象，就会在堆内存中开辟出一个新的空间，而变量保存_尚硅谷javascript新书大纲

ACM--HDOJ 2072--单词数--字符串--水_java acm单词数问题 #结束-程序员宅基地

文章浏览阅读1.2k次。HDOJ题目地址：传送门单词数Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 44934 Accepted Submission(s): 10992Problem Descr_java acm单词数问题 #结束

uniapp自定义tabbar必看_uniapp custom-tab-bar-程序员宅基地

文章浏览阅读9.5k次。方式一：实验证明，在根目录下新建custom-tab-bar目录，在目录中新建index.vue是行不通的，vue文件不会被编译方式二：将小程序四大法宝（wxss,json,wxml,js）直接搬过来，虽然tabbar有渲染在小程序上了，但是切换是没有效果的，所以还是行不通方式三（行得通）经过上面的两个尝试，还是乖乖的以vue的做法吧，用单页面的形式，通过v-show控制组件的隐藏和显示注意：v-show有时没有效果，因为v-show是通过display:none来控制的，它的权重没_uniapp custom-tab-bar

树莓派系列-3-连接到树莓派_树莓派片选接到-程序员宅基地

文章浏览阅读1.3k次。我们用树莓派，估计是没有人会接着屏幕使用的，但是如果有需求也可以使用。如果我们不用屏幕来使用树莓派，那么就得使用SSH、VNC、还有我们的Windows远程工具了。1.SSH 需要在树莓派中开启SSH支持，开启SSH支持有多种方式，这里我就说说我用的，第一种就是在我们烧写有系统的时候，在boot的分区里面新建一个不带任何后缀的ssh文件，最简单的方式就是新建txt文件，完了重命名为s..._树莓派片选接到

【毕业设计】STM32化工厂系统-程序员宅基地

文章浏览阅读32次。整个系统以STM32 单片机作为核心控制器，通过DHT11检测温湿度，通过CO传感器检测CO浓度，通过火焰传感器检测火焰，通过红外传感器检测人，通过RFID模块检测刷卡，检测到的数据通过OLED显示并通过无线传输模块上传数据到手机APP，通过继电器控制水阀，通过蜂鸣器报警。

CSS三角、界面样式(cursor、input输入边框不改变颜色、textarea拖拽不改变大小)、vertical-align、溢出文字省略号显示、CSS初始化_html css input::cue-程序员宅基地

文章浏览阅读1.5k次，点赞2次，收藏7次。vertical-align的可选值为：1. bottom: 图片的底线和文字的底线对齐，2. baseline：默认，图片的底线和文字的基线对齐，3. middle: 图片的中线和文字的中线对齐，4. top：图片的顶线和文字的顶线对齐。不同浏览器对有些标签的默认值是不同的，为了消除不同浏览器对HTML文本呈现的差异，所以需要进行CSS初始化。当我们选择input输入框，进行文字输入的时候，边框会改变颜色。textarea默认可以在右下角进行拖拽，改变输入框的大小。CSS初始化参考如下。_html css input::cue