求一个数列的子集（c/c++）
编写一个递归函数，用来输出n 个元素的所有子集。例如，三个元素{a, b, c} 的所有子集是：{ }（空集），{a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。
我对这个用递归，没什么思路，请大家帮帮忙

[解决办法]
给出完整代码和注释吧……

#include <iostream>
#include <vector>

using namespace std;

bool IsSubSetOnList( const vector <vector <int> > Src, const vector <int> & Sub )
{
for( int i=0; i <static_cast <int> (Src.size()); ++i )
{
if( Src[i].size() != Sub.size() )
continue;
bool IsEqual = true;
for( int j=0; j <static_cast <int> (Src[i].size()); ++j )
{
if( Src[i][j] != Sub[j] )
IsEqual = false;
};
if( IsEqual == true )
return true;
};
return false;
};

vector <vector <int> > SubSet( const vector <int> & SrcSet )
{
if( SrcSet.size() == 1 ) // 只有一个元素则返回，结束递归
return vector <vector <int> > ( 1, vector <int> ( 1, SrcSet[0] ) );
// 用于返回的子集集
vector <vector <int> > ret;
int Count = static_cast <int> (SrcSet.size() );
// 对每个元素
for( int i=0; i <Count; ++i )
{
// 剔除该元素生成Count-1的子集
vector <int> Src( Count -1 );
for( int j=0; j <(Count-1); ++j )
{
if( j <i )
Src[j] = SrcSet[j];
else
Src[j] = SrcSet[j+1];
};
// 加入该子集
ret.push_back( Src );
// 调用递归函数求该子集的所有子集。
vector <vector <int> > Sub = SubSet( Src );
for( int j=0; j < static_cast <int> (Sub.size()); ++j )
{
// 如果子集已在返回列表中，不加入
if( IsSubSetOnList( ret, Sub[j] ) )
continue;
// 否则加入该子集
ret.push_back( Sub[j] );
};
};
// 自己也是一个子集
ret.push_back( SrcSet );
return ret;
};

测试：

int main()
{
vector <int> MySet(5);
for( int i=0; i <5; ++i )
{
MySet[i] = i;
};
vector <vector <int> > Sub = SubSet( MySet );
cout < < Sub.size() < < endl;
for( int i=0; i <static_cast <int> (Sub.size()); ++i )
{
cout < < "{ ";
for( int j=0; j <static_cast <int> (Sub[i].size()); ++j )
{
cout < < Sub[i][j];
if( (j!=static_cast <int> (Sub[i].size()-1)) )
cout < < ", ";
}
cout < < " } ";
cout < < endl;
};
system( "pause " );
return 0;
};

结果：
31
{ 1, 2, 3, 4 }
{ 2, 3, 4 }
{ 3, 4 }
{ 4 }
{ 3 }
{ 2, 4 }
{ 2 }
{ 2, 3 }
{ 1, 3, 4 }
{ 1, 4 }
{ 1 }
{ 1, 3 }
{ 1, 2, 4 }
{ 1, 2 }
{ 1, 2, 3 }
{ 0, 2, 3, 4 }
{ 0, 3, 4 }
{ 0, 4 }
{ 0 }
{ 0, 3 }
{ 0, 2, 4 }
{ 0, 2 }
{ 0, 2, 3 }
{ 0, 1, 3, 4 }
{ 0, 1, 4 }
{ 0, 1 }
{ 0, 1, 3 }
{ 0, 1, 2, 4 }
{ 0, 1, 2 }
{ 0, 1, 2, 3 }
{ 0, 1, 2, 3, 4 }
[解决办法]
给一个实现，算法上很简单，lz仔细想想就能看懂，仅供参考

#include <stdio.h>

void subset (char * set, int * mask, int size, int c)
{
if (c == size)
{
//we get a result, output it
printf ( "{ ");
for (int i = 0; i < size; i++)
if (mask[i] == 1)

printf ( "%c ", set[i]);
printf ( "}\n ");
}
else
{
//select the cth element
mask[c] = 1;
//process the remainning elements
subset (set, mask, size, c + 1);

//unselect the cth element
mask[c] = 0;
//process the remaining elements
subset (set, mask, size, c + 1);
}
}


int main ()
{
char set[] = { 'a ', 'b ', 'c '};
int mask[3];

subset (set, mask, 3, 0);

return 0;
}
[解决办法]
我也给一个
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

char ** combine;
int combineSize = 0;

void combination(char *array1, int size)
{
if( size == 1 )
{
char *temp = (char *)malloc(sizeof(*temp)*(size+1));
temp[0] = array1[size-1];
temp[1] = '\0 ';
combine[combineSize++] = temp;
}
else
{
combination(array1, size-1);
int saveSize = combineSize;
for( int i = 0; i < saveSize; ++i)
{
int malSize = strlen(combine[i])+2;
char *temp = (char *)malloc(sizeof(*temp)*(malSize));
strcpy(temp,combine[i]);
temp[malSize-2] = *(array1+size-1),temp[malSize-1] = '\0 ';
combine[combineSize++] = temp;
}
char *temp1 = (char*)malloc(sizeof(*temp1)*2);
temp1[0] = *(array1+size-1),temp1[1] = '\0 ';
combine[combineSize++] = temp1;
}
}

int main()
{
combine = (char **)malloc(sizeof(*combine)*15);
combination( "ABCD ", 4);

for(int i = 0; i < combineSize; ++i)
{
printf( "{%s}\n ",combine[i]);
}
return 0;
}