求和为某个数的元素(DFS)
#include <iostream>#include <cstdio>#define MAX 10000using namespace std;int n = 0, M = 0;bool flag[MAX];int f[MAX];int sum = 0;int s[3];int DFS(int i) { printf("DFS(%d)\n", i); getchar(); if (i > 2) { return 0; } for (int j = 0; j < n; j++) { if (!flag[j] && sum<M) { flag[j] = true; sum = sum + f[j]; printf("s[%d] = %d\n", i, f[j]); printf("sum = %d\n", sum); s[i] = f[j]; if (sum==M && i==2) { return 1; } if (1 == DFS(i+1)) { return 1; } flag[j] = false; sum = sum - f[j]; s[i]= 0; } } printf("!!!\n"); return 0;}int main(){ while (2 == scanf("%d%d", &n, &M)) { for (int i = 0; i < n; i++) { scanf("%d", &f[i]); } int res = DFS(0); if (1 == res) { for (int i = 0; i < 3; i++) { printf("%d ", s[i]); } } else { printf("hello\n"); printf("-1"); } printf("\n"); } return 0;}/*********************5 72 4 5 3 1**************/#include <iostream>#include <cstdio>#define MAX 10000using namespace std;int n = 0, M = 0;bool flag[MAX];int f[MAX];int sum = 0;int s[3];int DFS(int i) { printf("DFS(%d)\n", i); getchar(); if (i > 2) { return 0; } for (int j = 0; j < n; j++) { if (!flag[j] && sum<M) { flag[j] = true; sum = sum + f[j]; printf("s[%d] = %d\n", i, f[j]); printf("sum = %d\n", sum); s[i] = f[j]; if (sum==M && i==2) { return 1; } if (1 == DFS(i+1)) { return 1; } flag[j] = false; sum = sum - f[j]; s[i]= 0; } } printf("!!!\n"); return 0;}int main(){ while (2 == scanf("%d%d", &n, &M)) { for (int i = 0; i < n; i++) { scanf("%d", &f[i]); } int res = DFS(0); if (1 == res) { for (int i = 0; i < 3; i++) { printf("%d ", s[i]); } } else { printf("hello\n"); printf("-1"); } printf("\n"); } return 0;}/*********************5 72 4 5 3 1**************/#include <iostream>#include <cstdio>#define MAX 10000using namespace std;int n = 0, M = 0;bool flag[MAX];int f[MAX];int sum = 0;int s[3];int DFS(int i) { printf("DFS(%d)\n", i); getchar(); if (i > 2) { return 0; } for (int j = 0; j < n; j++) { if (!flag[j] && sum<M) { flag[j] = true; sum = sum + f[j]; printf("s[%d] = %d\n", i, f[j]); printf("sum = %d\n", sum); s[i] = f[j]; if (sum==M && i==2) { return 1; } if (1 == DFS(i+1)) { return 1; } flag[j] = false; sum = sum - f[j]; s[i]= 0; } } printf("!!!\n"); return 0;}int main(){ while (2 == scanf("%d%d", &n, &M)) { for (int i = 0; i < n; i++) { scanf("%d", &f[i]); } int res = DFS(0); if (1 == res) { for (int i = 0; i < 3; i++) { printf("%d ", s[i]); } } else { printf("hello\n"); printf("-1"); } printf("\n"); } return 0;}/*********************5 72 4 5 3 1**************/