Sum It Up
这道题看似简单,但是也不好做,我试了多种方法均以失败告终。一看别人的代码,才知道什么是高手……
题的意思是从n个数中挑k个,使其和为m,求出所有情况。又像是一个DFS,但我一写许多细节问题就处理不好了,各种问题,无奈放弃 ,在Discuss发现一很短的代码,很惊异,下来后仔细研读,才领会到高超的技艺(向deathspeaker大牛致敬)。
先上代码吧:
#include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <string> #include <cstdio> #include <climits> using namespace std; int ans[12], n, k, data[12], f; void search(int i, int s) { int j; if (!s) { for (f = j = 1, printf("%d", ans[0]); j < k; j++) printf("+%d", ans[j]); printf("/n"); return; } if (i >= n || s < 0) return; for (j = i; j < n; j++) if (j == i || data[j] != data[j - 1]) { //这里的处理避免了重复的情况:data[j]!=data[j-1]) ans[k++] = data[j]; search(j + 1, s - data[j]); k--; } } int main() { int j, t; while (scanf("%d%d", &t, &n), t) { f = k = 0; for (j = 0; j < n; j++) scanf("%d", &data[j]); printf("Sums of %d:/n", t); search(0, t); if (!f) printf("NONE/n"); } return 0; }
这种题一般是当k看成定值,而变化累加得到的k',并在每次调用中比较二者,而此法则是变化k值,以一种化大为小的递归思路来解,另外还十分巧妙地解决了重复的问题,而且在我打算修改这代码时发现几乎没有什么可改的,风格和我的基本一致,有些细节牵一发而动全身,没有改的意义。实在佩服。
但是我感觉这方法未必是通法,不知是否能解决其他相似的问题。