给定 一个整数序列 a1 a2 a3 …..an 问能否从中选取若干个点，使他们的和恰好为K 1<=n<=20 第一种 -10^8<= ai <=10^8 -10^8<= K <=10^8 因为 题目中 的 ai和k 都可能是负数，所以只能够 用dfs 全排列 找到答案 第二种 0<= ai <=10^8 0<= k <=10^8 对于这个条件 ，就有多种求法了， 第一种 贪心
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<queue> #include<stack> #include<map> #include<vector> #define LL long long #define M 1000 #define inf 0x3f3f3f3f #define mod 100009 using namespace std; int arr[M]; int main() { int n,k; while(~scanf("%d%d",&n,&k)) { int i,j; for(i=0;i<n;i++) scanf("%d",&arr[i]); sort(arr,arr+n); for(i=n-1;i>=0;i--) { if(k>=arr[i]) k-=arr[i]; } if(sum) printf("No\n"); else printf("Yes\n"); } return 0; }还有一种就是 DFS ，但这个时候还可以进行剪枝 ，因为只要有一条路的当前值是大于k的，那么之后的路一定是不可行的，可以直接断了； 代码
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<queue> #include<stack> #include<map> #include<vector> #define LL long long #define M 1000 #define inf 0x3f3f3f3f #define mod 100009 using namespace std; int arr[M]; int n,k,flag; void dfs(int st,int sum) { int i,j; if(sum==k) { flag = 1 ; return ; } if(sum>k||st>n-1) return ; // sum>k 时return 剪枝 dfs(st+1,sum+arr[st+1]); dfs(st+1,sum); } int main() { while(~scanf("%d%d",&n,&k)) { int i,j; for(i=0;i<n;i++) scanf("%d",&arr[i]); flag=0; // 多组数据 注意重新赋值 dfs(-1,0); //不能从0 开始要不然就相当于 默认第一个数字是一定被加的 if(flag) printf("Yes\n"); else printf("No\n"); } return 0; }