poj 1564 Sum It Up -- DFS 递归

短命女 2022-10-14 10:55 5阅读 0赞

题意：给一个数 t ，以及 n 个数，求 n 个数中的几个数加起来的和为 t 的情况有多少种。

注意：题目要求相同的组合方式不能出现2次，即 “3 4 1 1 1 1 ” 的结果为：“1+1+1”。

思路：一个  for  循环遍历一遍，每个 i 表示以当前数为起点开始一次DFS递归，当所遍历的和为 t 时，输出该组合方式，如果大于 t 则返回，小于则往下递归。以二维数组保存已经输出过的数据，当又一次需要输出数据时，则需确认二维数组里没有改组数据（个人觉得还有更好的方法）。

#include<stdio.h>
    #include<string.h>
    int n,m,i,j,k,t,l;
    int data[20],vis[20],res[20],rear,flag,judge,save[20][20],num,count;// res数组保存当前的进行遍历的数据，save 数组则保存已经输出过的数据
    int dir[11]={1,2,3,4,5,6,7,8,9,10,11};
    void dfs(int x,int sum)
    {
    	if(sum>t) {return;}
       if(sum==t)
       {
    	   flag=0;
    	   for(l=0;l<num;l++)
    	   {
    		   count=0;
    		   for(j=0;j<rear;j++)
    			   if(save[l][j] == res[j]) count++; 
    			   if(count==rear) {flag=1;break;}
    	   }
    	   if(!flag)
    	   {
             for(j=0;j<rear;j++)
    			 save[num][j]=res[j];
    		 num++;
    		 for(j=0;j<(rear-1);j++)
               printf("%d+",res[j]);
             printf("%d\n",res[rear-1]); 
    	     judge=1;            // judge 为 1 表示输出过数据，为 0 则表示没输出过，则输出 “NONE” 
    	   }
    	   return;
       }
       for(k=0;k<n;k++) 
       {
    	    x=x+1;
    	    if(x>=n) return;  // 此处很关键！！！没加就WA，表示费解。
    	   if(x<n&&vis[x]==0)
    	   {
             vis[x]=1;
    	     res[rear++]=data[x];
    	     dfs(x,sum+data[x]);
    		 rear--; // rear 表示 res 数组的长度，当递归返回时（已经输出过一组数据，或者 和 大于 t ），需要减 1 。
    	     vis[x]=0;
    	   }
       }
    }
    int main()
    {
      while(scanf("%d%d",&t,&n)!=EOF && n!=0)
      {
        for(i=0;i<n;i++)
    		scanf("%d",&data[i]);
    	printf("Sums of %d:\n",t);
    	judge=0;num=0;
    	memset(save,0,sizeof(save));
    	for(i=0;i<n;i++)    // for 循环遍历一遍
    	{
    		memset(vis,0,sizeof(vis)); // 每一个 i 都是一个新的开始，vis 及 res 数组需要初始化
    		memset(res,-1,sizeof(res));
    		vis[i]=1;
    		rear=0;
    		res[rear++]=data[i];
    		dfs(i,data[i]);
    		vis[i]=0;
    	}
    	if(!judge) printf("NONE\n");
      }
      return 0;
    }