回溯法求解n个和为m的组合

2017-06-04 13:48 阅读 666 次 评论 0 条

本道题出自好未来的一道笔试题。题目的大概描述为:输入两个整数n和m,从数列1,2,3......n中随意取出几个数,使其和为m,要求列出所以可能的组合。

输入例子:

输出例子:

给大家看一张图吧,在VS2017下是可以成功运行的,并且结果也是正确的,此OJ的评测实在不敢恭维。

回溯法求解

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法。

此题我采用的数据结构为vector,创建两个vector数组,其中一个用于存储1~n,另一个用于存储可能出现的组合序列。大致过程如下(画图不好画,用数字模拟一下):

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:回溯法求解n个和为m的组合 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情