问题标题: 酷町堂：1047

题目链接： 酷町堂：1047

1047   子集和问题

经验值：1600 时间限制：1000毫秒 内存限制：128MB

题目描述 De**ion

子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。
对于给定的正整数的集合S={ x1， x2，…， xn}和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。
如果有多组子集和满足条件，只输出元素下标字典序最小的一组解。

输入描述 Input De**ion

第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1 行中，有n个正整数，表示集合S中的元素。

输出描述 Output De**ion

程序运行结束时，将子集和问题的解输出。当问题无解时，输出“No solution!”。

样例输入 Sample Input

5 10 2 2 6 5 4

样例输出 Sample Output

2 2 6

数据范围及提示 Data Size & Hint

n <= 10000

 

我的70分代码，求大佬找错

 

#include<bits/stdc++.h>

using namespace std;

int a[100010];

int pre[100010];

int vis[100010];

int tot =0;

int f =0;

int n,c;

void dfs(int p,int q)

{

if(f||p>q)return;//已经到头、已搜索到答案

 

vis[p] =1;

tot+=a[p];

 

if(tot == c)//已经搜索到答案

{

f =1;

int j=0;

for(int i=1; i<=p; i++)

{

if(j ==0 &&vis[i]){cout<<a[i];j++;}

else if(vis[i])cout<<" "<<a[i];

}

cout<<endl;

return;

}

 

if(tot+pre[n]-pre[p] <c) return;//已经没必要继续

//go

if(tot<c)dfs(p+1,n);

//back

tot-=a[p];

vis[p] =0;

dfs(p+1,n);

 

}

int main()

{

 

cin>>n>>c;

for(int i=1; i<=n; i++)

{

cin>>a[i];

pre[i]+=pre[i-1]+a[i];

}

if(pre[n]<c)

{

cout<<"No Solution!"<<endl;

return 0;

}

dfs(1,n);

return 0;

}