求组合数： 求n个数（1....n）中k个数的组合....
如：combination(5,3)
要求输出：543，542，541，532，531，521，432，431，421，321

给定一个数组，这个数组中既有正数又有负数，找出这个数组中的子数组，此子数组的和最大！

#include <stdio.h>
int data[100] = {5,4,3,2,1};
bool foot[100] = {0};
int cool = 0;
void com(int n,int k,int mem[],int depth,int begin)
{
    int i,j;
    if(k == depth)
    {
        for(i = 0;i<k;i++)
            printf("%d ",mem[i]);
        cool++;
        printf("\n");
        return ;
    }
    for(i = 0;i<n;i++)
    {
        if(!foot[i])
        {
            foot[i] = true;
            mem[begin] = data[i];
            com(n,k,mem,depth+1,begin+1);
            foot[i] = false;
        }
    }
}
int main()
{
    int mem[100] = {0};
    com(5,3,mem,0,0);
    return 0;
}

以上程序完成 A(m,n)并且将其打印出来

#include <stdio.h>
int data[100] = {5,4,3,2,1};
bool foot[100] = {0};
int cool = 0;
void com(int n,int k,int mem[],int depth,int begin,int pos)
{
    int i,j;
    if(k == depth)
    {
        for(i = 0;i<k;i++)
            printf("%d ",mem[i]);
        cool++;
        printf("\n");
        return ;
    }
    for(i = pos;i<n;i++)
    {
        if(!foot[i])
        {
            foot[i] = true;
            mem[begin] = data[i];
            com(n,k,mem,depth+1,begin+1,i+1);
            foot[i] = false;
        }
    }
}
int main()
{
    int mem[100] = {0};
    com(5,3,mem,0,0,0);
    return 0;
}

上面程序完成了 C(m,n)并且将其打印出来

[ 本帖最后由 laoyang103 于 2012-3-23 21:27 编辑 ]

仔细观察两个程序的递归 全排列的递归为无序生成子树 也就是每次都要从0一直到n来寻找

没有使用过的数  求解组合数时使用有序递归生成子树 也就是每次从上一次递归的下一个位置开始即i+1

这样就可以生成组合数  其实只是全排列稍稍改动一下

#include<stdio.h>
int main()
{
    int i,j,k;
    int b,c,n;
    while(EOF != scanf("%d",&n))
    {
        if(0 == n)
            break;
        int a[10001] = {0};
        int max[10001] = {0};
        int begin = 0,end = 0,tempmax = -1;
        int tempbegin = 0;
        for(i = 1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(1 == i)
            {
                max[i] = a[i];
                tempmax = max[i];
                tempbegin = begin = end = i;
            }
            else
            {
                if(max[i-1]>=0)
                {
                    max[i] = max[i-1]+a[i];
                }
                else
                {
                    max[i] = a[i];
                    tempbegin = i;
                }
                if(tempmax < max[i])
                {
                    tempmax = max[i];
                    end = i;
                    begin = tempbegin;
                }
            }
        }
        for(i = 1;i<=n;i++)
            if(a[i]>=0)
                break;
        if(i > n)
            printf("0 %d %d\n",a[1],a[n]);
        else
            printf("%d %d %d\n",tempmax,a[begin],a[end]);
    }
    return 0;
}

上面题是我在OJ上面做过的一道题 解法为动态规划  状态转移方程为

max[i] = max{max[i-1]+a[i],a[i]} 其实仔细看如果max[i-1]大于等于0那么一定是max[i-1]+a[i]

如果小于0 那么一定是a[i]所以可以写成 max[i] = max[i-1]>=0 ? max[i-1]+a[i]:a[i];

然后再从0到n去遍历max数组 找到那个最大值就可以了 题目网址http://acm.tzc.

应该能符合你的要求了吧

楼上经典，佩服，实在是厉害啊！

其实排列 组合这些算法都是递归的基础应用  递归更深的应用是搜索

第一题我也做了一下。

#include<stdio.h>
void combination(int n,int k);

static path[100]={0};
int cnt=0;

void main()
{
    combination(5,3);
}

void combination(int n,int k)
{
    if(n>=k)
    {
        if(n==k)
        {
            for(int i=n;i!=0;--i)
                path[cnt++]=i;
            for(i=0;i<cnt;i++)
                printf("%d",path[i]);
            printf(" ");
            cnt-=n+1;
            return;
        }
        if(k==0)
        {
            for(int i=0;i<cnt;i++)
                printf("%d",path[i]);
            printf(" ");
            cnt--;
            return;
        }
        if(k==1)
        {
           
            for(int i=n;i!=0;--i)
            {
                path[cnt++]=i;
                combination(i,0);
            }
            cnt--;   
        }
        else
        {
            path[cnt++]=n;
            combination(n-1,k-1);
            combination(n-1,k);
        }
    }
    else
        printf("data error!\n");
}

第二个是不是只要找出所有正数就可以了呢?

第二个不是找正数就行了。因为它应该是要这个数列的一个连续的部分，否则就完全没有考的意义了。

不过就从语言描述上看，子数组这个词确实有待商榷。
数学的数列是有子列的概念的，那个可没要求连着取，只要原来在前面的项还在前面就行了(就是说项的先后顺序不能换，其它的不关心)。


另外老杨经验丰富的很，给的答案很有参考价值。