典型的深搜,剪枝的时候需要跳过曾经搜索过的相同的数目,既满足nums[i]=nums[i-1]&&visit[i-1]==0,visit[i-1]==0可以说明该点已经测试过。
#include <stdio.h>
#include <string.h> #define MAXNUM 1005 int nums[MAXNUM];
int visit[MAXNUM];
int t, n; void output() {
int i, j=; for (i=; i<t; ++i) {
if (j && visit[i])
printf("+%d", nums[i]);
if (j== && visit[i]) {
printf("%d", nums[i]);
j = ;
}
}
printf("\n");
} int check(int index, int sum) {
if (index< || index>=t || visit[index] || sum+nums[index]>n)
return ;
return ;
} int dfs(int beg, int sum) {
int i, val=; if (sum == n) {
output();
return ;
} for (i=beg; i<t; ++i) {
if (i>beg && nums[i]==nums[i-] && visit[i-]==)
continue;
if (check(i, sum)) {
visit[i] = ;
if (dfs(i+, sum+nums[i]))
val = ;
visit[i] = ;
}
} return val;
} int main() {
int i; while (scanf("%d%d", &n, &t)!=EOF && (n||t)) {
for (i=; i<t; ++i)
scanf("%d", &nums[i]);
memset(visit, , sizeof(visit));
printf("Sums of %d:\n", n);
if ( !dfs(, ) )
printf("NONE\n");
}
return ;
}