求整数的各个组合之和（栈和队列）

求整数的各个组合之和（栈和队列）

时间： 1ms        内存：1000M

描述：

题目：输入两个整数 m 和n，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.

输入：

输入：6

输出：

输出：

6

5 1

4 2

3 2 1

示例输入：

6

示例输出：

6

5 1

4 2

3 2 1

提示：

参考答案（内存最优[752]）：

#include<stdio.h>   
#include<malloc.h> 
#include<string.h> 
#define SEN 100   
      
struct sqstack   
{   
    char *base;   
    char *top;   
    int size;   
};   
      
struct sqstack *initEmptyStack()   /*构建空輚*/
{   
    struct sqstack *p;   
    p=(struct sqstack *)malloc(sizeof(struct sqstack));   
    if(p!=NULL)   
    {   
        p->base=(char *)malloc(sizeof(struct sqstack)*SEN);   
        if(p->base!=NULL)   
        {   
            p->top=p->base;   
            p->size=SEN;   
            return p;   
        }   
    }   
    else
        free(p);   
    return NULL;   
}   
      
int push(struct sqstack *p,int a)         /*入栈*/
{   
    *p->top++=a;   
    return 0;   
}   
      
int gettop(struct sqstack *p)             /*取栈顶元素*/
{  
    if(p->base!=p->top)  
        return *(p->top-1);  
    return 0; 
} 


int pop(struct sqstack *p)              /*出栈*/
{   
    return *(--p->top);   
}   
      
int main()   
{    
    struct sqstack *p1,*p2,*p3;
	int m,t=1,a,sum,n;
	scanf("%d",&m);
	p1=initEmptyStack();
	p2=initEmptyStack();
	p3=initEmptyStack();
	printf("%d\n\n",m);
	n=m;
	m--;
	while(m--)
	{
		sum=0;
		t=1;
		do{
			push(p1,t);
				t++;
		}while(t<=m+1);
		while(p1->base!=p1->top)
		{
			a=pop(p1);
			sum+=a;
			if(sum>n)
				sum-=a;
			else if(sum==n)
			{
				while(p2->base!=p2->top)
					push(p3,pop(p2));
				while(p3->base!=p3->top)
					printf("%d ",pop(p3));
				printf("%d\n\n",a);
				sum-=a;
			}
			else
				push(p2,a);
		}
		while(p2->base!=p2->top)
			pop(p2);
	}
	return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int length;
void ff(int n,int m,int *flag)
{
    if(n < 1 || m < 1)return;
    if(n > m)n = m;
    if(n == m)
    {if(n!=length)
        printf("\n");
        flag[n-1] = 1;
        for(int i=length-1,j=0; i>=0; i--)
            if(flag[i] == 1)
            {
                printf(j==0?"%d":" %d",i+1);
                j=1;
            }
        printf("\n");
        flag[n-1] = 0;
    }
    flag[n-1] = 1;
    ff(n-1,m-n,flag);
    flag[n-1] = 0;
    ff(n-1,m,flag);
}
int main()
{
    int m;
    scanf("%d",&m);
    length=m;
    int *flag = (int*)malloc(sizeof(int)*m);
    ff(m,m,flag);
    free(flag);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。