求算法：满足条件的排列组合解决方法

求算法：满足条件的排列组合
假设有一个随机数列{1,2，3，4，5....}
求其中相加为100的所数有组合，比方{{1,99},{1,2,97},{4,96}......}


自己想了一天，找不到解决办法。求师兄们指点

------解决方案--------------------
类似于背包问题,递归来实现吧.
每个数字都可以选择2中状态,在组合里和不在组合里.
------解决方案--------------------
#define ARRAY_SIZE (10)
int pArray[ARRAY_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int pPrint[ARRAY_SIZE];
int nPrintPos;
int nTempSum;
int nSum;


void CheckSum(int nPos)
{
int i;
if(nSum == nTempSum)
{
printf( "%d = ", nSum);
for(i=0; i <nPrintPos-1; i++)
{
printf( "%d + ", pPrint[i]);
}
printf( " %d\n ", pPrint[i]);
return;
}

if(nPos < ARRAY_SIZE)
{
if(nTempSum+pArray[nPos] <= nSum)
{
nTempSum += pArray[nPos];
pPrint[nPrintPos++] = pArray[nPos];
CheckSum(nPos+1);
nPrintPos--;
nTempSum -= pArray[nPos];
}
CheckSum(nPos+1);
}
}

int main()
{
nTempSum = 0;
memset(pPrint, 0, sizeof(int)*ARRAY_SIZE);
nPrintPos = 0;
scanf( "%d ", &nSum);

CheckSum(0);

return 0;
}

垃圾代码,仅供参考.
------解决方案--------------------
这样的问题用回溯法解决比较合适。

回溯法的效率瓶颈在于剪枝函数与限界函数的效率。

为了使回溯法的效率高，应该注意：
1：要有一个好的搜索次序。因此，将随机数列{1,2，3，4，5....}排序是有用的，因为这样剪枝函数就不盲目，更有效率。
2：在判断一个组合最后一个元素是否存在时，可用哈希表提高效率。比如：对一个三元组合，若已经确定前两个为1，2，现在要确定第三个元97是否在数列中，可用哈希查找。


另外，楼主所谓的“随机数列”，让人很不解。如果“随机数列”中有两个是一样的数，并且这个数包含在某个组合A中，那么A是算一个，还是两个？

------解决方案--------------------
那复杂度是2^n了，有没有更好的算法那？

------解决方案--------------------

回溯法：

#include <iostream>

using namespace std;

int list[20]={1,8,71,98,2,45,3,9,11,85,73,
5,61,54,38,79,28,18,21,31};
int Stack[10];
int Stacklen=0;
int s=0;

int GetMaxLen( )
{
int i=0, s=0;
while(s+list[i] <100)
s+=list[i++];
return i;
}

void Sort( )
{
int i, j, temp;
for( i=0; i <20; ++i )
{
for( j=i+1; j <20; ++j )
{
if( list[i]> list[j] )
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}
}

void Found( int f, int len, int sum )
{
int i;
if( len==0 )
{
if( s==100 )
{
cout < < "{ ";
for( i=0; i <Stacklen-1; ++i )
cout < <Stack[i] < < ", ";
cout < <Stack[i] < < "} " < <endl;
}
return ;
}
i=f;
while( list[i]+s <=100 && i <20 )
{
Stack[Stacklen]=list[i];
s+=list[i];
++Stacklen;
if( Stacklen==1 )
Found(f+1, len-1, sum-list[i]);
else
if(Stack[Stacklen-2] <Stack[Stacklen-1])
Found(f+1, len-1, sum-list[i]);

--Stacklen;
s-=list[i];
++i;
}
}

int main()
{
Sort();

int i, Maxlen=GetMaxLen();

for( i=2; i <=Maxlen; ++i )
Found( 0, i, 100 );

system( "PAUSE ");
return 1;
}

------解决方案--------------------