首页 > 代码库 > POJ 1564 经典dfs

POJ 1564 经典dfs

1、POJ 1564 Sum It Up   

2、总结:

题意:在n个数里输出所有相加为t的情况。

技术分享
#include<iostream>#include<cstring>#include<cmath>#include<queue>#include<algorithm>#include<cstdio>#define F(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=10010,MAX=1000100;bool flag;int t,n;int num[20],ans[20];void dfs(int cnt,int k,int sum){    if(sum==t){        flag=false;        F(i,1,cnt-1){            if(i==1)printf("%d",ans[i]);            else printf("+%d",ans[i]);        }        printf("\n");        return ;    }        //关键    F(i,k,n){        if(i==k||num[i]!=num[i-1]&&sum+num[i]<=t){              ans[cnt]=num[i];            dfs(cnt+1,i+1,sum+num[i]);        }    }}int main(){    while(~scanf("%d%d",&t,&n),t&&n)    {        flag=true;        F(i,1,n)scanf("%d",&num[i]);        printf("Sums of %d:\n",t);        dfs(1,1,0);        if(flag)printf("NONE\n");    }    return 0;}
View Code

 

POJ 1564 经典dfs