想了一个算法，不能验证正确与否，不过思路都写上了，希望有些用
程序代码：
/*描述
有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如：
n=5,5个数分别为1,2,3,4,5，t=5；
那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
输入
输入的第一行是两个正整数n和t，用空格隔开，其中1<=n<=20,表示正整数的个数，t为要求的和(1<=t<=1000)
接下来的一行是n个正整数，用空格隔开。
输出
和为t的不同的组合方式的数目。
*/
// 想来想去就想到了个递归。。。注释解释了一下算法，从main函数看是依次看
#include <stdio.h>
int sum = 0; // 这是结果，全局变量，初始化一定为0，开始计数后在别的地方不要改变其值
void Count(int *array, int n, int t,int s, int elmNum)
{ // 这是个递归函数，也是这个算法的核心部分，利用int指针array(你也可以
// 理解成数组名，但是这的的确确是指针，它们还是有一定区别的)，剩余数组个数
// n，调用函数前已经有的和s以及所需要的组合元素个数剩余个数elmNum的传递来实现
// 递归。
// 在执行这个函数前，在Process函数里面找到了maxNum的值，所以就是当elmNum为1至
// maxNum时，每次都调用Count函数，即调用：
// Count(a, n, t, 0, 1);
// Count(a, n, t, 0, 2);
// ...
// Count(a, n, t, 0, maxNum);
// 在这个时，a还是main函数里面数组名，也就是数组第一个元素的地址（在调用Process
// 函数时，已经把指针值--数组地址 传递给了a，就是上面的啊）；上面的n是main函数
// 输入的n的个数；此时刚刚调用Count函数，还没有开始计算，所以已有的和s还是0。
// 当最后那个参数，也就是elmNum是1时，说明再加上一个元素的值就能满足想要组合元素
// 的个数了，此时进行t与（s+某元素的值）的值比较，如果相等，就说明有一种情况符合，
// 进行sum++的操作。
//
// 下面重点来了：
// 如果，所需的elmNum大于1，那么在这一次的函数执行是不好把剩下的全部组合情况（是排列
// 组合的组合 意思自己理解就是 C A 那个）一一清查的，因为不确定elmNum的值，有可能
// 是3,4甚至更多。所以，想到利用递归，通过每调用一次Count函数减少elmNum的1的值，
// 直到elmNum为1，就用上面的思路求出来。
// 那么怎么排查，怎么依次把所有的情况都列出来呢？
// 说一下思路，当elmNum是一个确定值的时候，例如3，那么就是说t是由三个元素组合的（他
// 们都不重复，就先假设全部的数组假设就是1,2,3...10，t是10）。那么你可以想象，如果每
// 个组合都从小到大排列了一下（例如1,2,7；1,3,6；2,3,5等等）一定是从最小的1开始，
// 把有1的组合情况取出来，剩下组合情况再把有2取出来（这里面就没有1了，剩下的还没有
// 取出来的也没有2了），依次取到数组的最后一个元素。
// 这时候，取出来1就代表这个1已经是组合里面的一员了，组合的和s就是1，这时候1这个
// 元素就不参与剩下的组合情况的调配，这时候，剩下的elmNum就是2，剩下的数组就从2开
// 始，数组的地址也就把1这第一个元素的地址去掉然后从a+1（为什么不是a+sizeof(int)？
// 因为a是int类型指针，加1以后的访问是说加了一个int型数据长度以后的访问）开始，这
// 时候数组元素个数就是n-1。然后调用Count(a+1, n-1, t, 1, 2)开始递归。
// 而如果取出来的是2，那么就是说组合里面没有1，因为已经排查了，那么这时候：剩下
// 的elmNum就是2，剩下的数组就从3开始，数组的地址也就把1,2这两个元素的地址去掉然
// 后从a+2开始，剩余数组元素个数是n-1。然后调用Count(a+2, n-1, t, 2, 2)开始递归。
// 同上类情况，组合里面最小的数当依次是i=1,2,3...时候就能用个循环结构调用
// Count(a+1+i, n-1, t, s, 2);
// 注意，数组里面的1元素的下标是0所以传递指针是a+1+i,而和s要用s+a[i]表示加上了这个
// 数组元素，让下面的递归能够知道，好去判定最后与t的比较。
//
// 下面继续：
// 当1被取出来后，调用了Count(a+1, n-1, t, 1, 2)也就是调用了Count(a+1, 9, t, 1, 2)
// 就是说剩下两个元素要在main函数里面的后九个元素里面寻找，思路也是和上面3个找第
// 一个时一样（这也是为什么能用递归了，而且这里应该也能发现排序的好处，不排序算法不容
// 易实施）。然后找到了组合的第二个元素（这里的举例，组合需要三个），再通过循环找
// 第三个，这时候elmNum是1，就开始进行与t的比较了。
//
// 说一下碰到的特殊情况：
// if (n < elmNum)
// 这个是说剩余数组元素已经少于需要的元素个数，因为前面是循环进行递归的会把所有情况
// 都列出来，那么在这个例子里面有可能会调用Count(某地址, 0, t, 1, 2)，就没有剩下可选
// 的元素了，所以也不可能有符合条件的情况了，直接返回上一级循环，节约点时间，少出错。
// if (s + array[i] <= t)
// {
// Count(array + i + 1, n - i - 1, t, s + array[i], elmNum - 1);
// }
// 这里是要选择array[i]作为所需要的组合元素之一，不管剩下几个还没有找的元素，假如
// 此时s + array[i] > t 那么就可以不用执行下去了，已经大于t了不管怎么加都会一直大
// 于t（都是正整数，题目已经说明了）所以只有当s + array[i] <= t时候才继续下一个环
// 节的递归调用。
int i; // 循环计数变量
fprintf(stdout, "\n\n\n此时最大组合元素剩余%d个，数组元素剩余%d个，和是%d。\n",
elmNum, n, s);
if (n < elmNum)
{ // 一种特殊情况
fprintf(stdout, "此时剩余数组元素已经少于需要的元素个数，不成立。\n");
return;
}
if (1 == elmNum)
{ // elmNum为1时，进行判定
for (i = 0; i < n; i++)
{
if (s + array[i] == t)
{
sum++;
fprintf(stdout, "这是第%d种情况，和是%d,最后数组元素是%d。\n",
sum, s, array[i]);
}
}
}
else
{ // elmNum不是1时候递归调用
for (i = 0; i < n; i++)
{
if (s + array[i] <= t)
{ // else情况是另一种特殊情况，上面有说明
Count(array + i + 1, n - i - 1, t, s + array[i], elmNum - 1);
}
}
}
return;
}
void Process(int a[], int n, int t)
{ // 这是初步处理函数，为了求一下组合的最大个数，例如例子里面有
// 5 1,4 2,3 其实最大的组合个数是2。至于怎么求，就用到了刚才
// 排序的数组，你从最小的开始加，依次加下去如果加到的一个数，
// 加之前小于t，加之后大于t，那么这个maxNum就是这个数的数组下标
// 了。maxNum就是maxElementNumber，还是那个1,2,3,4,5的例子，1+2是3
// 小于t，1+2+3是6大于t，那么组成t最多也就是2个，正好是3的元素
// 下标（1的下标是0，往后依次是1,2...）。而且这已经是最小的组合了
// 相同数目的元素任意其他情况都比这种情况的和要大，所以这就是极限
// 情况了，然后就利用某些算法（我这里想到的是递归）依次求出来当组
// 合数是1个，2个...maxNum个的情况（sum是全局变量，一定初始化为0）。
int maxNum = 0; // 最大的个数组合可能的个数
int s = 0; // 求数组元素依次相加的和,别忘了初始化0
int i; // 循环计数变量
for (i = 0; i < n; i++)
{
s += a[i];
if (s > t)
{
maxNum = i;
break; // 找到满足条件值以后可以直接跳出循环体了
}
}
if ((n == i) && (sum < t))
{ // 一种特殊情况，如果输入数字是1,2,3 而所求和是10，就没有符合题意的组合了
fprintf(stdout, "\n所有值的和都小于要求t\n");
return;
}
if (0 == maxNum)
{ // 另一种特殊情况，如果maxNum是0，说明要么循环完没找到符合要求的下标，就是
// 上面那种情况，已经return了，另一种就是数组最小值比t大，那么也不可能有符
// 合题意的组合。
fprintf(stdout, "\n数组最小值都大于要求t\n");
return;
}
fprintf(stdout, "\nmaxNum是%d个。\n", maxNum);
for (i = 1; i <= maxNum; i++)
{ // 从1到maxNum开始调用这个Count函数
Count(a, n, t, 0, i);
}
return;
}
void main()
{
int n; // 数组个数
int t; // 所求组合的和
int i, j; // 循环计数变量
int temp; // 排序时候的中间变量
int array[20]; // 记录数组 因为说明不多于20个所以就定一个20个长度的
fprintf(stdout, "请输入数字个数与求和的值：");
fscanf(stdin, "%d%d", &n, &t);
for (i = 0; i < n; i++)
{ // 把数字录入数组里面，这个录入方式不严谨，如果是oj的话，可能这里会出问题
fprintf(stdout, "请输入第%d个数值：", i+1);
fscanf(stdin, "%d", &array[i]);
fprintf(stdout, "你输入的数值是：%d\n", array[i]);
// 上面一句其实就是怕输入流哪里出问题，容易验证
}
fprintf(stdout, "\n排序前的数组是：\n");
for (i = 0; i < n; i++)
{ // 排序前输出数组
fprintf(stdout,"%-4d", array[i]);
}
for (i = 0; i < (n - 1); i++)
{ // 排序，按顺序排序有利于算法实现。。
for (j = i + 1; j < n; j++)
{
if (array[i] > array[j])
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
fprintf(stdout, "\n排序后的数组是：\n");
for (i = 0; i < n; i++)
{ // 排序后输出数组，正好可以比较，顺便简单检查一下正误
fprintf(stdout,"%-4d", array[i]);
}
Process(array, n, t); // 调用处理函数，把n，t还有数组的首地址传过去
fprintf(stdout, "\n一共有%d种情况。\n", sum); // 输出结果，sum是开头定义的全局变量
}
坐等楼下
