蓝桥杯：算法训练 和为T 枚举与递归

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯：算法训练 和为T 枚举与递归，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1297字，纯文字阅读大概需要2分钟。

内容图文

问题描述
　　从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。
输入格式
　　第一行一个正整数n，表示整数集内元素的个数。
　　第二行n个整数，用空格隔开。
　　第三行一个整数T，表示要达到的和。
输出格式
　　输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。
　　若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。
　　最后一行输出总方案数。
样例输入
5
-7 -3 -2 5 9
0
样例输出
-3 -2 5
-7 -2 9
2
数据规模和约定
　　1<=n<=22
　　T<=maxlongint
　　集合中任意元素的和都不超过long的范围

由于T<=maxlongint 所以注意要用long long来保存整数. 看到题目直接暴力枚举并没有多想，0代表不取1代表取，枚举时当总和等于T就打印出来。由于多组解从不包含第n,n-1,n-2……开始打印，那么就要从最后一个数开始，倒着枚举.

#include <bits/stdc++.h>

using namespace std;

int n,a[22],flag[22],cnt;
long long sum;

void f(int tag,long long x){
	if(tag>=0){ //tag从n-1开始倒着枚举
		for(int i=0;i<=1;i++){//0代表不取 1代表取
			flag[tag]=i;
  			f(tag-1,i==1?x+a[tag]:x);
		}
	}
	else{//递归出口，若x==sum就打印.注意要避免一个数都没有取，总和x为0，但恰好sum=0的情况。 
		if(x==sum){
			int p=0;
			for(int j=0;j<n;j++){
				p+=flag[j];
			}
			if(p!=0){
				cnt++;
				for(int j=0;j<n;j++){
					if(flag[j]!=0){
						cout<<a[j]<<' ';
					}
				}
				cout<<endl;
			}
 	 	}
	}
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cin>>sum;
	f(n-1,0);
	cout<<cnt<<endl;
	return 0;
}

内容总结

以上是互联网集市为您收集整理的蓝桥杯：算法训练 和为T 枚举与递归全部内容，希望文章能够帮你解决蓝桥杯：算法训练 和为T 枚举与递归所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/854657.html

---

来源：【匿名】