Problem 25 || Subset Sum Problem using Backtracking in c++

  Subset Sum Problem using Backtracking in c++

by Ujjal Roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

void func(ll arr[],ll len,ll indx,vector<ll>&vec,ll sum)

{

    if(sum==0)

    {

        for(ll i=0;i<vec.size();i++)cout<<vec[i]<<" ";

        cout<<endl;

        return;

    }

    if(indx==len)

    {

        return;

    }

    func(arr,len,indx+1,vec,sum);

    if(arr[indx]<=sum)

    {

         vec.push_back(indx);

        func(arr,len,indx+1,vec,sum-arr[indx]);

        vec.pop_back();

    }

}

int main()

{

    ll n,sum;

    cin>>n>>sum;

    ll arr[n];

    ll i;

    for(i=0;i<n;i++)

    {

        cin>>arr[i];

    }

    vector<ll>vec;

    func(arr,n,(ll)0,vec,sum);

}