Generate all Subset sums of an array in vector type function

#include <bits/stdc++.h>
using namespace std;

void func(vector<int> a, int N, vector<int&subsets, int f, long long sum){
    // to make use of recursion in any type of complex 
    // function other than void, make a spare void
    // function for execution.

    // select pointer pos and then make a choice
    //  of taking it or not in the sum and proceed with 
    // that two choices upto f != N. The recursion tree
    //  at the end will have all the possible chocies.

    if(f == N){
        subsets.push_back(sum);
        return;
    }

    // yes: take the element into sum
    func(a, N, subsets, f+1, sum + a[f]);

    // No: dont take element 
    func(a, N, subsets, f+1, sum);

}

vector<intsubsetSums(vector<int> arr, int N){
    vector<int> ans;
    func(arr, N, ans, 00);
    sort(ans.begin(), ans.end());

    return ans;
}

int main(){
    // generate sum of subsets of an array 
    // in ascending order with a pre given 
    // vector type function.

    cout << "Ready" << endl;
    int N;
    cin >> N;
    vector<intarr(N);
    for(int i=0;i<N;i++) cin >> arr[i];

    vector<int> ans = subsetSums(arr, N);
    for(auto value: ans) cout << value << " ";

    return 0;
}



Comments

Popular Posts