文档章节

IT公司100题-21-输入n和m,和等于m

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/12/30 17:02
字数 345
阅读 83
收藏 3

问题描述:

输入两个整数n 和m,从数列1,2,3,…,n 中随意取几个数, 使其和等于m,将所有可能的组合都打印出来。

 

问题分析:

利用递归的思路,对于1,2,3,…,n 中的任意一个数,要么选,要么不选。递归下去,直到其和等于m时,输出。

代码实现:

// 21.cc
#include <iostream>
#include <cstring>
using namespace std;

void print(int* aux, int n) {
	for (int i = 1; i <= n; i++)
		if (aux[i])
			cout << i << " ";
	cout << endl;
}

void helper(int m, int cur, int* aux, int n) {
	if (m == 0){
		cout << "Got one: " << endl;
		print(aux, n);
		//if equal, no need to calculate further recurse
		//cause, further add will make it unequal
		return;
	}
	// m<0 for select, but sum too big
	//cur > n for selection out of range
	if (m < 0 || cur >  n){
		//cout << "calulate: " << endl;
		//for (int i = 1; i <= n; i++)
		//	cout << aux[i] << " ";
		//cout << endl;
		return;
	}

	// unselect cur
	helper(m, cur + 1, aux, n);

	// select cur
	aux[cur] = 1;
	helper(m - cur, cur + 1, aux, n);
	aux[cur] = 0;  // backout 
}

void find_combi(int n, int m) {
	if (n > m) 
		find_combi(m, m);
	else {
		int* aux = new int[n];  // aux[i] = 1 represent selected
		memset(aux, 0, n * sizeof(int));
		helper(m, 1, aux, n);
	}
}

int main() {
	int n, m;
	cout << "input n and m:" << endl;
	cin >> n >> m;
	find_combi(n, m);
	return 0;
}

代码输出:

input n and m:
10 10
Got one: 
10 
Got one: 
4 6 
Got one: 
3 7 
Got one: 
2 8 
Got one: 
2 3 5 
Got one: 
1 9 
Got one: 
1 4 5 
Got one: 
1 3 6 
Got one: 
1 2 7 
Got one: 
1 2 3 4


© 著作权归作者所有

关西大汉弹琵琶
粉丝 8
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
从1加到100的算法你会吗?那从第M加到第N呢?

今天在看视频教程的时候,听到“杨中科”老师说有很多大公司,在面试的时候常常问一些基础的东西,甚至常问你一些简单到“变态”的题,对于我们做Web开发来说,突然问你一些算法题,也许有好...

布雷泽
2011/04/27
0
0
HDU 2010 水仙花数 水题 解法

HDU 2010 水仙花数 水题 解法 博主刚开始练习ACM,打算时时刻刻记录下自己的进步,并和大家做分享,希望大家能多多指教。 题目: 春天是鲜花的季节,水仙花就是其中最迷人的代表,数学上有个...

zyq975522483
2017/04/12
0
0
Python 基础练习 PAT水题(四)

#学习笔记 #用以练习python基础 # 原题链接:https://www.patest.cn/contests/pat-b-practise/1050 1050. 螺旋矩阵(25) 本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“...

chaunceyjiang
2017/04/26
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
重磅分享:微软等数据结构+算法面试100题全部答案完整亮相

引言 无私分享造就开源的辉煌。 今是二零一一年十月十三日,明日14日即是本人刚好开博一周年。在一周年之际,特此分享出微软面试全部100题答案的完整版,以作为对读者的回馈。 一 年之前的1...

云栖希望。
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【2019年8月版本】OCP 071认证考试最新版本的考试原题-第9题

Choose three Which three statements are true about views in an Orade batabase? A) A SELECT statement cannot contain a where clause when querying a view contaning a WHERE clause ......

oschina_5359
39分钟前
5
0
[JSON].connectionValue()

本文转载于:专业的前端网站➭[JSON].connectionValue() 语法: [JSON].connectionValue() 说明: 将对象的所有键值接连成新的字符串值 返回: [String] 示例: Set a = toJson()c = Array(1,2,...

前端老手
41分钟前
4
0
云计算给大数据分析工具带来了什么

如果大数据是一块蛋糕,那么大数据分析工具就是切蛋糕的刀叉。人们都期待着能用“刀叉”从大数据中挖出自己想要的“价值”,因此大数据分析工具被人们寄予厚望。而云计算技术的兴起似乎又给大...

青果云小潘
43分钟前
4
0
centOS7下es的使用

安装启动es7.4.0 docker pull docker.elastic.co/elasticsearch/elasticsearch:7.4.0docker run -d -p 9200:9200 -e "discovery.type=single-node" docker.elastic.co/elasticsearch/elast......

无畏的老巨人
50分钟前
4
0
iptables删除命令中的相关问题

最近在做一个中间件的配置工作,在配置iptables的时候,当用户想删除EIP(即释放当前连接),发现使用iptables的相关命令会提示错误。iptables: Bad rule (does a matching rule exist in t...

xiangyunyan
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部