问题描述
输入一个含有不同数字的序列,输出其所有子集合(含空集)。要求:1)集合里元素有序排列;2)输出结果不含有重复集合
举例
输入序列{3,1,2}
输出:{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
问题分析
可以使用排列组合问题求解的第一种方法:分期摊还。初始化时,结果集合里含有一个空集。当扫描数列时,保留原有集合,同时将当前元素插入现有的所在集合中,从而形成新的集合。详见后面代码的GetSubSetsAmortized函数。
也可以使用第二种方法:for循环中使用递归。注意:1)保留任意的中间结果,而不是遍历完成数列才保存结果。2)利用完了数列的数之和,需要回退,即回溯法,恢复至使用前的状态。详见后面代码的GetSubSetsRecursive函数。
扩展问题
如果序列中含有重复元素,又要保证输出结果不含重复集合,如何处理?为了避免输出重复组合,只取第一个相同的元素加入组合中。详见后面代码的GetSubSetsRecursiveEx函数。
代码部分
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef vector<int> IntArray;
typedef vector<vector<int>> ResultSet;
ResultSet gResultSet;//结果集
//采用分期摊还的方法
void GetSubSetsAmortized( const IntArray& mSrcArray )
{
//加入空集
gResultSet.push_back( IntArray() );
for( int i = 0; i < mSrcArray.size(); ++i )
{
int nCount = gResultSet.size();
for( int j = 0; j < nCount; ++j )
{
IntArray mSubSet = gResultSet[j];
mSubSet.push_back( mSrcArray[i] );
gResultSet.push_back( mSubSet );
}
}
}
//采用for循环内递归调用
void GetSubSetsRecursive( const IntArray& mSrcArray, IntArray& mDstArrayTemp, int iStart )
{
if ( iStart > mSrcArray.size() ) return;
gResultSet.push_back( mDstArrayTemp );//保留任意的中间结果
for( int i = iStart; i < mSrcArray.size(); ++i )
{
//加入元素
mDstArrayTemp.push_back( mSrcArray[i] );
GetSubSetsRecursive( mSrcArray, mDstArrayTemp, i + 1 );
//移除元素
mDstArrayTemp.pop_back();
}
}
//采用for循环内递归调用
void GetSubSetsRecursiveEx( const IntArray& mSrcArray, IntArray& mDstArrayTemp, int iStart )
{
if ( iStart > mSrcArray.size() ) return;
gResultSet.push_back( mDstArrayTemp );//保留任意的中间结果
for( int i = iStart; i < mSrcArray.size(); ++i )
{
//避免结果集重复,只取第一个相同值加入
if ( i != iStart && mSrcArray[i] == mSrcArray[i-1] ) continue;
//加入元素
mDstArrayTemp.push_back( mSrcArray[i] );
GetSubSetsRecursiveEx( mSrcArray, mDstArrayTemp, i + 1 );
//移除元素
mDstArrayTemp.pop_back();
}
}
//打印结果集
void OutSubSets()
{
for( ResultSet::iterator it = gResultSet.begin();
it != gResultSet.end(); ++it )
{
if ( it->empty() )
{
cout << "空集" << endl;
continue;
}
for( IntArray::iterator itTemp = it->begin();
itTemp != it->end(); ++itTemp )
{
cout << *itTemp << " ";
}
cout << endl;
}
cout << "--------------------------------------------" << endl;
}
int main()
{
IntArray mSrcArray;
int nTemp;
while( true )
{
mSrcArray.clear();
while( cin >> nTemp )
{
if ( nTemp == 0 ) break;
mSrcArray.push_back( nTemp );
}
//排序
sort( mSrcArray.begin(), mSrcArray.end() );
gResultSet.clear();
//GetSubSetsAmortized( mSrcArray );
IntArray mDstArrayTemp;
GetSubSetsRecursiveEx( mSrcArray, mDstArrayTemp, 0 );
//打印结果集
OutSubSets();
}
return 0;
}
系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟,那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷,程序员面试揭秘》一书而写的一些心得体会,文章大多数观点均来自此书,特此说明!
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.
作者:山丘儿