poj 1564

9551 단어 poj
  • Source Code
    /*
    
     * Author:lonelycatcher
    
     * problem:ZOJ 1711
    
     * Type: DFS
    
     */
    
    #include<iostream>
    
    #include<stdio.h>
    
    #include<queue>
    
    #include<string>
    
    #include<string.h>
    
    using namespace std;
    
    int t,n;
    
    struct node
    
    {
    
    	int data;
    
    	int preindex;
    
    };
    
    node lis[15];
    
    int OK,count;
    
    void printpath(int index)
    
    {
    
    	if(lis[index].preindex==-1)
    
    	{
    
    	   printf("%d",lis[index].data);
    
    	}
    
    	else
    
    	{
    
            printpath(lis[index].preindex);
    
            printf("+%d",lis[index].data);
    
    	}
    
    }
    
    void DFS(int index,int presum)
    
    {
    
       if(presum>t)return ;
    
       if(presum==t)
    
       {
    
    	   OK=1;
    
           printpath(index);
    
           cout<<endl;
    
           return ;
    
       }
    
       for(int i=index+1;i<=n;i++)
    
       {
    
    	   lis[i].preindex=index;
    
    	   DFS(i,presum+lis[i].data);
    
    	   lis[i].preindex=-1;
    
    	   while(i<=n && lis[i].data==lis[i+1].data)i++;
    
       }
    
    }
    
    int main()
    
    {
    
    	setbuf(stdout,NULL);
    
    	int i;
    
    	while(scanf("%d %d",&t,&n)!=EOF)
    
    	{
    
    		if(t==0&&n==0)break;
    
    		OK=0;
    
    		for(i=1;i<=n;i++)
    
    		{
    
    			scanf("%d",&lis[i].data);
    
    		    lis[i].preindex=-1;
    
    		}
    
    		printf("Sums of %d:
    ",t); for(i=1;i<=n;i++) { lis[i].preindex=-1; DFS(i,lis[i].data); while(i<=n && lis[i].data==lis[i+1].data)i++; } if(!OK) { printf("NONE
    "); continue; } } return 0; }
  • 좋은 웹페이지 즐겨찾기