Print All Paths With Target Sum Subset


1. You are given a number n, representing the count of elements.
2. You are given n numbers.
3. You are given a number "tar".
4. You are required to calculate and print true or false, if there is a subset the elements of which add up to "tar" or not.
5. Also, you have to print the indices of elements that should be selected to achieve the given target.
6. You have to print all such configurations.

Input Format

A number n
n1
n2
.. n number of elements
A number tar

Constraints
1 <= n <= 30
0 <= n1, n2, .. n elements <= 20
0 <= tar <= 50
Sample Input
5
4
2
7
1
3
10
Sample Output
true
2 4 
1 2 3 
0 1 3 4 
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)          \
    for (auto x : a)      \
        cout << x << " "; \
    cout << endl
#define print1(a)    \
    for (auto x : a) \
    cout << x.F << " " << x.S << endl
#define print2(a, x, y)         \
    for (int i = x; i < y; i++) \
        cout << a[i] << " ";    \
    cout << endl

inline int power(int a, int b)
{
    int x = 1;
    while (b)
    {
        if (b & 1)
            x *= a;
        a *= a;
        b >>= 1;
    }
    return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}

const int N = 200005;

struct node
{
public:
    int n, target;
    string path;
    node(int row, int tar, string psf)
    {
        n = row;
        target = tar;
        path = psf;
    }
};

void solve()
{

    int n;
    cin >> n;
    vi v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    int k;
    cin >> k;
    vector<vector<bool>> dp(n + 1, vector<bool>(k + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= k; i++)
        dp[0][i] = false;
    for (int i = 1; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (j < v[i - 1])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = (dp[i - 1][j] | dp[i - 1][j - v[i - 1]]);
        }
    }
    if (dp[n][k])
        cout << "true\n";
    else
        cout << "false\n";

    queue<node> q;
    q.push({n, k, ""});

    while (!q.empty())
    {
        node f = q.front();
        q.pop();

        if (f.n == 0 || f.target == 0)
            cout << f.path << endl;
        else
        {

            if (f.target >= v[f.n - 1])
            {
                bool inc = dp[f.n - 1][f.target - v[f.n - 1]];
                if (inc)
                    q.push({f.n - 1, f.target - v[f.n - 1], to_string(f.n - 1) + " " + f.path});
            }
            bool exc = dp[f.n - 1][f.target];
            if (exc)
                q.push({f.n - 1, f.target, f.path});
        }
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    clock_t z = clock();

    int t = 1;
    //   cin >> t;
    while (t--)
        solve();

    return 0;
}