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

问题描写叙述

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

要求：

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

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

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

举例：

输入{2。3。4。7}，目标值为7

输出{7}。{2。2，3}。{3，4}

问题分析

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

同这里我们使用递归的方法来解决这个组合问题，即典型的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;
}