HDU 1258 Sum It Up

题目链接~~>

                   开始时没想道怎样判重，后来想到用二维数组存一下一个值的所有组合，当前值如果再出现别的组合，先检查一下存入的是否有重复的，如果没有则输出，否则不输出，然后检查下一个值时，如果与上一个组合过的值相同，那么只需要判断是否与上一个产生的组合有重复的。据说可以用哈希表判重。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int n,m,p,sut,f ;
     
    
   

    

     

    
    

     

      int g[15],a[100][15],b[100],vis[15] ;
     
    
   

    

     

    
    

     

      void dfs(int cut,int sum)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i ;
     
    
   

    

     

    
    

     
 if(sum==m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int k=0,sx=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++) // 先把找到的组合存储起来
     
    
   

    

     

    
    

     
 if(vis[i])
     
    
   

    

     

    
    

     

       a[p][k++]=g[i] ;
     
    
   

    

     

    
    

     

       b[p++]=k ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<p-1 ;i++)  //判断是否有重复的
     
    
   

    

     

    
    

     
 if(b[i]==k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx=1 ;
     
    
   

    

     

    
    

     
 for(int j=0 ;j<k ;j++)
     
    
   

    

     

    
    

     
 if(a[i][j]!=a[p-1][j])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sx=0 ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(sx)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!sx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sut=1 ; // 标记是否有解
     
    
   

    

     

    
    

     
 for(i=0 ;i<k ;i++)
     
    
   

    

     

    
    

     
 if(!i)
     
    
   

    

     

    
    

     
 printf("%d",a[p-1][i]) ;
     
    
   

    

     

    
    

     
 else printf("+%d",a[p-1][i]) ;
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else p-- ;
     
    
   

    

     

    
    

     
 return  ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(cut==n)
     
    
   

    

     

    
    

     
 return  ;
     
    
   

    

     

    
    

     
 for(i=cut ;i<n ;i++)
     
    
   

    

     

    
    

     
 if(g[i]+sum<=m&&!vis[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[i]=1 ;
     
    
   

    

     

    
    

     

       dfs(cut+1,g[i]+sum) ;
     
    
   

    

     

    
    

     

       vis[i]=0 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i ;
     
    
   

    

     

    
    

     
 while(scanf("%d %d",&m,&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!n)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     
 int sm=0 ; sut=0 ; p=0 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     

       sm+=g[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     
 for(i=0 ;i<n ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(sm<m)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     
 memset(vis,0,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       f=0 ;
     
    
   

    

     

    
    

     
 if(i!=0&&g[i]!=g[i-1])
     
    
   

    

     

    
    

     

       p=0 ;
     
    
   

    

     

    
    

     

       sm-=g[i] ; vis[i]=1 ;
     
    
   

    

     

    
    

     

       dfs(i+1,g[i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!sut)// sut==0 表示无解
     
    
   

    

     

    
    

     
 printf("NONE\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/14455997