算法练习:排列组合之组合和

算法练习:排列组合之组合和

问题描写叙述

给出一组不同的正整数序列和一个目标值,求出全部可能的组合,使得组合里全部元素和为目标值。

要求:

1)每一个组合里的元素依照升序排列。

2)输出组合里不含有反复的组合。

3)输入序列中的整数能够多次使用。

 

举例:

输入{2347},目标值为7

输出{7}{223}{34}

 

问题分析

为了让输出元素按升序排列,可对输入序列进行排序。

同这里我们使用递归的方法来解决这个组合问题,即典型的for语句内调用递归函数。须要注意下面几点:

1)记录剩余目标值和,仅仅有当该值为0时。组合才是有效的。

2)记录当前位置,由于序列中的数能够反复使用,所下面一次递归时,还能够从当前位置開始。这将体如今递归函数的參数里。

详细可參看代码实现中的GetResultSet函数。

 

扩展问题

假设序列中可能有同样的元素。而且每一个元素最多仅仅能使用一次,那么又该怎么处理?相对于之前的问题,这里有两个变化:1)每一个元素最多仅仅能使用一次,下次递归时是不能从当前位置開始的,而是从下一个開始。2)因为序列中含有相等的元素,哪怕每一个元素最多仅仅使用一次,也可能出现反复的组合,所以。为了避免反复,仅仅取第一个同样元素。

详细可參看代码实现中的GetResultSetEx函数。

 

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<int> IntArray;
 

//结果集
typedef vector<vector<int>> ResultSet; 
ResultSet gResultSet;

//原始序列中不含同样的值
void GetResultSet( const IntArray& mSrcArray, int nTarget, 
				  IntArray& mDstArray, int iStart )
{
	if ( nTarget < 0 ) return;
	if ( nTarget == 0 )
	{
		//找到一个结果
		gResultSet.push_back( mDstArray );
	}
	else
	{
		for( int i = iStart; i < mSrcArray.size(); ++i )
		{
			//后面更大的数不可能满足条件
			if ( mSrcArray[i] > nTarget ) break;

			//增加当前元素
			mDstArray.push_back( mSrcArray[i] );

			//递归处理。由于元素能够反复使用,所以从当前位置继续递归
			GetResultSet( mSrcArray, nTarget-mSrcArray[i], mDstArray, i );

			//重置
			mDstArray.pop_back();
		}
	}
}

//序列中可能有同样的元素。而且每一个元素最多仅仅能使用一次。不含反复组合
void GetResultSetEx( const IntArray& mSrcArray, int nTarget, 
				  IntArray& mDstArray, int iStart )
{
	if ( nTarget < 0 ) return;
	if ( nTarget == 0 )
	{
		//找到一个结果
		gResultSet.push_back( mDstArray );
	}
	else
	{
		for( int i = iStart; i < mSrcArray.size(); ++i )
		{
			//后面更大的数不可能满足条件
			if ( mSrcArray[i] > nTarget ) break;

			//避免结果集反复。仅仅取第一个同样值增加结果中
			if ( i != iStart && mSrcArray[i] == mSrcArray[i-1] ) continue;

			//增加当前元素
			mDstArray.push_back( mSrcArray[i] );

			递归处理。由于元素能够反复使用,所以从当前位置继续递归
			//GetResultSet( mSrcArray, nTarget-mSrcArray[i], mDstArray, i );

			//递归处理,由于元素不能够反复使用,所以从下一位置继续递归
			GetResultSetEx( mSrcArray, nTarget-mSrcArray[i], mDstArray, i+1 );

			//重置
			mDstArray.pop_back();
		}
	}
}


//输出结果集
void OutPutResultSet()
{
	if ( gResultSet.size() <= 20 )
	{
		for( ResultSet::iterator it = gResultSet.begin(); 
			it != gResultSet.end(); ++it )
		{
			for( IntArray::iterator itTemp = it->begin(); 
				itTemp != it->end(); ++itTemp )
			{
				cout << *itTemp << " ";
			}
			cout << endl;
		}
		
	}
	cout << "总共结果数:" << gResultSet.size() << endl;
	cout << "---------------------------------------" << endl;
}


int main()
{
	IntArray mSrcArray;
	IntArray mDstArrayTemp;
	int nTarget = 0;
	
	while( true )
	{
		//构造源数据
		int nTemp = 0;
		mSrcArray.clear();
		while( cin >> nTemp )
		{
			if ( nTemp == 0 ) break;
			mSrcArray.push_back( nTemp );
		}
		cin >> nTarget;

		//从小到大排序
		sort( mSrcArray.begin(), mSrcArray.end() );

		mDstArrayTemp.clear();
		gResultSet.clear();
		//GetResultSet( mSrcArray, nTarget, mDstArrayTemp, 0 );
		GetResultSetEx( mSrcArray, nTarget, mDstArrayTemp, 0 );

		//输出结果
		OutPutResultSet();
	}
	return 0;
}

 算法练习:排列组合之组合和算法练习:排列组合之组合和

系列文章说明:
1.本系列文章[算法练习],不过本人学习过程的一个记录以及自我激励,没有什么说教的意思。

假设能给读者带来些许知识及感悟。那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷。程序猿面试揭秘》一书而写的一些心得体会,文章大多数观点均来自此书,特此说明!

3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者:山丘儿
转载请标明出处。谢谢。

原文地址:http://blog.csdn.net/s634772208/article/details/46710405

 

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109171.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 屏蔽了网页里的二维码怎么取消_怎么把手机转成网页版

    屏蔽了网页里的二维码怎么取消_怎么把手机转成网页版最近在做微信公众号的开发,在菜单加入外部链接时,点击后一直提示“非微信官方网页,将由微信转换为手机预览模式”,请问怎么去掉这个提示页面直接进去外部链接?解决方法:设置一下业务域名即可,一共可以设

  • pycharm使用小技巧_pycharm基本使用方法

    pycharm使用小技巧_pycharm基本使用方法Pycharm作为Python开发最常用的IDE之一,不仅兼容性好,而且功能也相当丰富,比如调试、语法高亮、智能提示等等功能,它还支持web开发框架比如Django等,当你熟悉了它之后,开发效率是相当之高的。但对于新手来说,Pycharm功能丰富的同时也是一把双刃剑,有的小伙伴刚上手之后看到一堆的英文界面难免会懵逼,哈哈哈,没有关系,今天博主就来教大家一些Pycharm最常用的技巧,以及一些pycharm常用的快捷键,让你快速上手Python开发中最常用的IDEPycharm,跟上老司机的车速!一

  • FastClick源码分析

    FastClick源码分析玩过移动端web开发的同学应该都了解过,移动端上的click事件都会有300毫秒的延迟,这300毫秒主要是浏览器为了判断你当前的点击时单击还是双击,但有时候为了更快的对用户的操作做出更快的响应,越过这个300毫秒的延迟是有点必要的,faskclick做的就是这件事,这篇文章会理清faskclick的整体思路,分析主要的代码,但不会贴出所有的代码,仅分析主干,由于历史原因,faskclick对旧版本…

  • 语义分割 实例分割 全景分割_语义分割转实例分割

    语义分割 实例分割 全景分割_语义分割转实例分割之前看过一篇使用分割思想进行目标检测,所以这里补习下一些分割相关的基础知识。这里重点说下语义分割、实力分割和全景分割的区别。1、semanticsegmentation(语义分割)通常意义上的目标分割指的就是语义分割,图像语义分割,简而言之就是对一张图片上的所有像素点进行分类语义分割(下图左)就是需要区分到图中每一点像素点,而不仅仅是矩形框框住了。但是同一物体的不同实例不需要单独分…

  • Jquery delegate 在iPhone的safari下有bug

    Jquery delegate 在iPhone的safari下有bug使用delegate注册事件时,iphone的safari不能冒泡到body上,

    2022年10月19日
  • 学习NodeJS第一天:node.js介绍

    学习NodeJS第一天:node.js介绍

    2021年12月17日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号