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

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

智能推荐

ideaSSM 高校公寓交流员管理系统bootstrap开发mysql数据库web结构java编程计算机网页源码maven项目-程序员宅基地

文章浏览阅读1.3k次，点赞19次，收藏25次。一、源码特点idea 开发 SSM 高校公寓交流管理系统是一套完善的信息管理系统，结合SSM框架和bootstrap完成本系统，对理解JSP java编程开发语言有帮助系统采用SSM框架（MVC模式开发），系统具有完整的源代码和数据库，系统主要采用B/S模式开发。前段主要技术 bootstrap.css jquery后端主要技术 SpringMVC spring mybatis数据库 mysql开发工具 IDEA JDK1.8 TOMCAT 8.5。

C语言实现顺序表_顺序表c语言实现-程序员宅基地

文章浏览阅读1.6k次，点赞36次，收藏39次。1.2 SeqList.c1.3 test.c二、顺序表的实现2.1 顺序表创建一个顺序表结构体，成员包含顺序表地址、长度、大小，用于创建顺序表变量。将顺序表变量的地址传参，通过指针接收对顺序表的顺序表数组初始化为空，长度为0，大小为0。同样传地址，要先断言指针是否为空，不然会出异常。然后判断顺序表大小是否为0，为0则代表顺序表中没有有效元素，打印提示，并返回函数，如果大于0，则有元素，从下标0开始，打印size个顺序表元素，并用空格相隔。当我们结束程序_顺序表c语言实现

谈谈ChatGPT对中国教育的影响与挑战，我们该怎么办？_chatgpt对教育的弊端-程序员宅基地

文章浏览阅读1.8k次。他们需要制定明确的指导政策，提供必要的培训资源，保护学生数据隐私，定期评估和收集反馈，以及推广批判性思维和信息素养的教育。他们需要教育学生如何正确使用这个工具，鼓励他们自主学习，监管他们的使用行为，教育他们保护数据隐私和安全，以及提供充足的社交环境。ChatGPT可以用作一个强大的辅助学习工具，帮助学生理解复杂的概念，解答疑难问题，或者为他们的学习提供个性化的建议。在一些资源匮乏的地区，这可能是一个挑战。家长需要监督孩子的ChatGPT使用情况，确保他们在使用这个工具的同时，也在进行其他重要的学习活动。_chatgpt对教育的弊端

vuepress 打包：window is not defined_vuepress的config.js打包报错referenceerror: window is no-程序员宅基地

文章浏览阅读1.8k次。vuepress 打包报错：window is not defined_vuepress的config.js打包报错referenceerror: window is not defined at useconfi

JavaEE框架学习笔记——SpringMVC篇，面试互联网公司怎么说-程序员宅基地

文章浏览阅读472次，点赞5次，收藏17次。学完之后，若是想验收效果如何，其实最好的方法就是可自己去总结一下。比如我就会在学习完一个东西之后自己去手绘一份xmind文件的知识梳理大纲脑图，这样也可方便后续的复习，且都是自己的理解，相信随便瞟几眼就能迅速过完整个知识，脑补回来。下方即为我手绘的MyBtis知识脑图，由于是xmind文件，不好上传，所以小编将其以图片形式导出来传在此处，细节方面不是特别清晰。但可给感兴趣的朋友提供完整的MyBtis知识脑图原件（包括上方的面试解析xmind文档）

@RequestParam与不加@RequestParam的区别_@requestparam(required = true) 和 @requestparam-程序员宅基地

文章浏览阅读587次。public String providerList(@RequestParam(value="queryProName",required=false,defaultValue="")String queryProName, @RequestParam(value="queryProCode",required=false,defaultValue="")String queryProCode, @RequestParam(value="pageIndex",required=false,_@requestparam(required = true) 和 @requestparam

随便推点

How Firewalls (Security Gateways) Handle the Packets? (Traffic Flow)-程序员宅基地

文章浏览阅读167次。Different firewall (security gateway) vendor has different solution to handle the passing traffic. This post compiles some useful Internet posts that interpret major vendors’ solutions including:1. C..._traffic@flow: nat:

基础设施即代码（Infrastructure as Code）-程序员宅基地

文章浏览阅读4.3k次，点赞2次，收藏7次。Infrastructure as Code（IaC）是一种IT基础设施管理流程，它将DevOps软件开发的最佳实践应用于云基础设施资源的管理。_infrastructure as code

Android二维码的创建、解析及NotFoundException_no multiformat readers were able to detect the cod-程序员宅基地

文章浏览阅读1.8k次。本篇博客主要记录一下Android生成及解析二维码的基本方法，同时记录一下遇到的NotFoundException及对应解决方法。_no multiformat readers were able to detect the code.

java里nim游戏问题_使用Minimax算法的NIM游戏和AI玩家 - AI会失去动作-程序员宅基地

文章浏览阅读182次。我已经完成了与人类玩家和AI玩家一起编写NIM游戏的任务 . 该游戏是“Misere”(最后一个必须选择一根棒) . 人工智能应该是使用Minimax算法，但它正在进行移动，使其失去更快，我无法弄清楚为什么 . 我已经连续几天走到了尽头 . Minimax算法的目的是不输，如果它处于失败状态，延迟失去尽可能多的动作，对吧？考虑以下：NIMBoard board =新的NIMBoard(34,2)..._nim的 misere版本

MyBatis 中常用的 Mapper 相关注解和技巧，包括 @Select/@Insert/@Update/@Delete 和 @Options，并给出一些常见的优化方法_mapper @select-程序员宅基地

文章浏览阅读1.6k次。Mapper 是 MyBatis 中的一个重要概念，它用于封装复杂的 SQL 和参数映射关系，降低数据访问层与业务逻辑层之间的耦合度，方便后期维护和扩展。本系列教程主要基于 MyBatis3.x版本进行讲解，对 MyBatis-spring、MyBatis-mybatis、MyBatis-generator 等其他框架也会有所涉及。在 MyBatis 中，Mapper 是一个接口，这个接口提供了若干个方法，这些方法对应了我们执行数据库操作时需要执行的 SQL 语句或存储过程。_mapper @select

day01：Python安装详细教程_python 安装详细教程 csdn-程序员宅基地

文章浏览阅读35次。2023年最新Python安装详细教程。_python 安装详细教程 csdn