子集和问题#include<stdio.h>
#include<algorithm>
using namespace std;
int b[70001],n,c;//n（元素个数） c （目标值）
int a[70001];
bool next(int i,int sum,int w,int c){//深度优先搜索（dsf）
if(i>=n+1){
if(sum==c){
return true;
}else{
return false;
}
}
if(sum>c||sum+w<c){
return false;
}
a[i+1]=1;
if(next(i+1,sum+b[i+1],w-b[i+1],c)) return true;
a[i+1]=0;
//if(next(i+1,sum,w-b[i+1],c))
return next(i+1,sum,w-b[i+1],c);
}
int main(){
int sum=0,w=0,temp,i;
scanf("%d%d",&n,&c);
int j;
for(j=1;j<=n;j++){
scanf("%d",&b[j]);
w=w+b[j];
}
for(i=1;i<=n;i++){//冒泡排序，排序一下更方便
for(j=1;j<n;j++){
if(b[j]>b[j+1]){
temp=b[j]; b[j]=b[j+1];
b[j+1]=temp;
}
}
}
//sort(b,b+n);
//for(j=1;j<=n;j++){
//printf("%d",b[j]);
//}
if(next(0,0,w,c)){
for(j=1;j<=n;j++){
if(a[j]==1) printf("%d ",b[j]);
}
printf("\n");
}else{
printf("No Solution!\n");
}
return 0;
}
运用dsf（深度优先搜索和递归，不喜勿喷