背政治背的太阳穴发疼，连啃着苹果都会自觉想到人与自然的对立统一。黑格尔先生、马克思先生、还有很多很多先生，若是在天有知，定会被几百年后的中国大学生精英们感动到流泪口牙。

    好吧，做一道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");
}

评论