2065174 2006-09-13 21:04:57 Accepted 1711 C++ 00:00.00 436K St.Crux     背政治背的太阳穴发疼，连啃着苹果都会自觉想到人与自然的对立统一。黑格尔先生、马克思先生、还有很多很多先生，若是在天有知，定会被几百年后的中国大学生精英们感动到流泪口牙。     好吧，做一道1/2弱题换换脑子。题目还是很弱的，普通的搜索，几个数之和凑成M，不允许有重复出现。之所以加个头衔，是因为当初在学校比赛里做的时候用了很白痴的手段：把搜出来的结果换成string放到一个vector里，后来者要和先到的做比较......这有够烂的了。但在当时是我狗急跳墙，哦不，是灵机一动下的大彻大悟。     但是如今就大不同哦。在清华版《数据结构》的理论光环指引下（注：这是广告），我写下了简洁的方法。     举一个例子。     M = 13。有六个数： 6, 5, 5, 2, 2, 2。     13 = 6 + 5 + 2     显然，搜完第一个2之后，下一个2应该被忽略。然而在搜索里总不能写if(a[i] != 2)吧。因为如果M是15，第二个2是必须的。这个处理困惑了我好久——查理曼的后代称之为Hanter，Angle-Sexons（盎格鲁萨克森人，又译棱角分明的性感男人）改进为Haunt，后来流传到中国称作「鬼啊」——这是迷信的象征。总之就是莫明其妙的出错。     后来仔细的研究了几种遍历。发现如果这里采用后序遍历——也就是先记录子节点再记录根节点的话，问题就迎刃而解了。     考虑上面的例子。遍历时顺序是这样的：2，5，6。这很好的解释了为什么第二个2不需要了——当回溯到5时只要看一下子节点记录（2）就知道了。注意，回溯。规律同样适用于6和5。     比如M＝15。M＝6+5+2+2。但是没有回溯。当第二个2做完之后，第三个2加不了，因为17>15。于是回溯。这时5的子节点是2，然后K掉第三个2。 #include <cstdio>#include <string> int n, m, r[12], a[12], f, c, l;    //r保存结果，a保存输入。c表示r的长度，即搜索的深度。l记录上一个遍历的点。 void init();void dfs(int, int);void print(); int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) && n) {  printf("Sums of %d:\n", n);  int i;  for(i = 0; i < m; i ++)  {   scanf("%d", &a[i]);  }  init();  dfs(-1, 0);  if(!f)   printf("NONE\n"); } return 0;}    void init(){ memset(r, 0, sizeof(r)); f = 0, c = -1, l = 0;} void dfs(int i, int sum){ c ++; if(sum == n)  print(); else {  int ii = i + 1;  for( ; ii < m; ii ++)  {   if(a[ii] + sum <= n && a[ii] != l)   {    r[c] = a[ii];    dfs(ii, sum + a[ii]);   }  } } if(i != -1)  l = a[i]; c --;} void print(){ f = 1; int i; for(i = 0; i < c; i ++) {  if(i)   printf("+");  printf("%d", r[i]); } printf("\n");}

评论