子集和问题

给定n个不同的正整数集合w=（w1，w2，…，wn）和一个正数W，要求找出w的子集s，使该子集中所有元素的和为W。

输入格式:

第一行输入n和W，第二行依次输入n个数。

输出格式:

每行输出一个符合要求的子集。

输入样例1:

4 31
11 13 24 7

输出样例1:

11 13 7 
24 7 

#include<bits/stdc++.h>
using namespace std;
int n,res;
vector<int> v,v1;
//vector类似数组，但是它可以自动初始化
//函数，如果sum>res,pos>n就结束，如果不成立，就把这些数加起来
//相等就输出
void dfs(int sum,int pos){
    if(pos>n) return;//return;表示结束
    sum += v[pos];
    if(sum>res)
        return;
    v1.push_back(v[pos]);
    if(sum==res){
        for(auto it=v1.begin();it!=v1.end();it++){
            //auto等价于vector<int>::iterator
            cout<<*it<<" ";
        }
        cout<<endl;
    }
    for (int i = pos + 1; i <= n;i++){
        dfs(sum, i);
    }
    v1.pop_back();
}
int main(){
    cin>>n>>res;
    v.resize(n+1);//resize()的作用是改变vector中元素的数目
    //因为下面的循环为1-n;如果改为0-(n-1)会产生段错误
    for(int i=1;i<=n;i++) cin>>v[i];
    for(int i=1;i<=n;i++)
        dfs(0, i);//sum=0,pos随i变动
    return 0;
}