(From http://community.csdn.net/Expert/topic/3971/3971377.xml?temp=.7857324)
1.从已知数组d的前n个元素中找出部分元素序列之和等于total的元素序列,约定数组的元素都是正整数,且都小于等于total。
解答：这个题可以用递归进行穷举。
假设
实现以上方法的函数为 int GetTotal(int *a_piArr,int a_in,int m_iTotal,int i_iIndex)。
其中
函数返回值为能够得到的个数，
const int *const a_piArr为数组的首地址，
const int a_in为从前n个元素中找，
const int m_iTotal为需要找的和,
int a_iNowTotal 为目前的和，
int a_iIndex 为目前的第index个数值，
int *const a_iTmpArr存放找到的几个数值的index,
int a_iTmpCnt存放目前的a_iTmpArr中存放的元素个数。
int GetTotal(const int* const a_piArr,const int a_in,const int a_iTotal,int a_iNowTotal,int a_iIndex,int * const a_iTmpArr,int a_iTmpCnt)
{
static int iRet = 0;
int i;
if(a_iIndex >= a_in || a_iNowTotal > a_iTotal)
{
return iRet;
}
while(a_iIndex < a_in)
{
while((a_iIndex < a_in) && (a_iNowTotal + a_piArr[a_iIndex] > a_iTotal))
{
a_iIndex ++;
}
if(a_iIndex >= a_in)
{
return iRet;
}
if(a_iNowTotal + a_piArr[a_iIndex] < a_iTotal)
{
a_iTmpArr[a_iTmpCnt] = a_iIndex;
GetTotal(a_piArr,a_in,a_iTotal,a_iNowTotal + a_piArr[a_iIndex],a_iIndex + 1,a_iTmpArr,a_iTmpCnt + 1);
}else // =
{
a_iTmpArr[a_iTmpCnt] = a_iIndex;
for(i = 0; i <= a_iTmpCnt; i ++)
{
cout<<a_iTmpArr[i] <<":"<< a_piArr[a_iTmpArr[i]] <<" " ;
}
cout << endl;
}
a_iIndex ++;
} // end while(a_iIndex < a_in)
return iRet;
}
例如：
在main()中运行如下语句：
int iTmp[n];
int id[] = {2,5,5,2,5,6,3};
int iTotal = 12;
int iRet;
iRet = GetTotal(id,n,iTotal,0,0,iTmp,0);
即会将数组id[]的前5个数中和等于12的几个值的序号和值打印出来。
(完毕)
