t0ur1st

题目描述：

子集和问题的一个实例为<S,t>。其中S={x1, x2, …, x3}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得。试设计一个解子集和问题的回溯法。对于给定的正整数的集合S = {x1, x2, …, xn}和正整数c，计算S的一个子集S1，使得。

输入描述：

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

输出描述：

若问题有解则将子集和问题的解输出，否则输出”No Solution!”。

输入样例：

5 10
2 2 6 5 4

输出样例：

2 2 6

解题思路：

用自定义函数findSubsetSum来判断子序列是否存在题解。逐个访问子序列中的元素，用子集和sum累加子序列中的元素，若sum恰好等于子集和c的目标值就return true，若sum大于子集和的值就不对当前元素进行累加。当访问的下标cur大于子序列的元素个数时就开始进行回溯，直到sum=c时为止，若回溯到cur=0了还没有得到sum=c，就说明该子序列无解。

代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for (int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int maxn = 1001;
int n,c;    //n表示集合S大小,c是子集和目标值
bool vis[maxn];
vector<int> v;
bool findSubsetSum()
{
    int cur = 0,sum = 0;   //当前访问下标cur,子集和sum
    while(cur >= 0)
    {
        if(!vis[cur])
        {
            vis[cur] = true;
            sum += v[cur];
            if(sum == c) return true;
            else if(sum > c)
            {
                sum -= vis[cur];
                vis[cur] = false;
            }
            cur++;
        }
        if(cur >= v.size())
        {
            while(vis[cur-1])
            {
                cur--;
                vis[cur] = false;
                sum -= v[cur];
                if(cur == 0) return false;
            }
            while(!vis[cur-1])
            {
                cur--;
                if(cur == 0) return false;
            }
            vis[cur-1] = false;
            sum -= v[cur-1];
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(vis, false);
    cin >> n >> c;
    Up(i,1,n)
    {
        int _;
        cin >> _;
        v.push_back(_);
    }
    if(findSubsetSum())
    {
        int cnt = 0;
        Up(i,0,n-1)
        {
            if(vis[i])
            {
                cout << (cnt++==0?"":" ") << v[i];
            }
        }
    }
    else
    {
        cout << "No Solution!" << endl;
    }
    return 0;
}