Sum it up

题意：给定一个数sum,和n个数，求sum可以由这n个数里面的那几个数的和表示。

Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four different sums that equal 4: 4,3+1,2+2, and 2+1+1.(A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

注意：输入，输出要求比较高，另外不能有重复。

​ 递归的时候应该及时退出。

http://acm.hdu.edu.cn/showproblem.php?pid=1258

#include<cstdio>

#include<iostream>

int sum,n;

int flag=0;

int a[20],ans[20];

void  dfs(int sums,int cut,int x)//sums代表当前的和，cut代表ans里的[1,cut),x代表a中的第x个数

{

    if(sums==sum){

        for(int i=1;i<cut;i++){

            flag=1;

            if(i==cut-1)

                printf("%d\n",ans[i]);

            else

                printf("%d+",ans[i]);

        }

        return ;

    }//如果结果sums==sum按格式输出ans 并且flag=1;

    int t=-1;

    for(int i=x;i<=n;i++){

        if(t!=a[i]){

            ans[cut]=a[i];

            t=a[i];//避免重复

            dfs(sums+a[i],cut+1,i+1);

        }

    }//

    return ;//递归要有结束条件，不能是return;

}

int main ()

{

    while(scanf("%d %d",&sum,&n),n||sum)

    {

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        flag=0;

        printf("Sums of %d:\n",sum);

        dfs(0,1,1);

        if(flag==0)

            printf("NONE\n");

    }

    return 0;

}