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<int> subsetSums(vector<int> arr, int N){
vector<int> ans;
func(arr, N, ans, 0, 0);
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<int> arr(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
Post a Comment