Sum it up problem

#1

how to handle the duplicacy

#2

Hello @Bansaljatin05

To handle duplicacy you can use a map.
Convert the combination to a string
Like convert {1, 5, 16} to “1 5 16” and insert it to the map.
So even if the combination {1, 5, 16} appear two times, it would only be inserted once.

Then once all the combinations are inserted, print all the elements from the map.

You should also sort the array first before doing anything because that will make things easier for you.
When any combination is formed, it will be in the sorted order only.

If you need any further help, just leave a reply to this thread.

1 Like
#3

sir but maps are not covered yet in the course, is there any other way to handle

#4

if we have to use maps , then can you tell me how i can do that

#5

Hello @Bansaljatin05

Here is the code.

Try to dry run this code on some test case and understand it.
If you won’t be able to understand the code, just leave a reply and I will get back to you.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#7

here is the solution to the problem.

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

set<vector> mp;
void sum_it_up(vector out,vector&a,ll i,ll t,ll n)
{
//base case
if(t==0)
{
if(mp.find(out)==mp.end())mp.insert(out);
return;
}
if(i>=n)return;

 //recurrsive case

 if(a[i]<=t)
 {
	 out.push_back(a[i]);
	 sum_it_up(out,a,i+1,t-a[i],n);
	 out.pop_back();
 }

 sum_it_up(out,a,i+1,t,n);

}
int main() {
ll int n,t;
cin>>n;
vectorout;vectorv;
for(int i=0;i<n;i++)
{
ll int x;
cin>>x;
v.push_back(x);
}
cin>>t;
sort(v.begin(),v.end());
//for(auto a:v)cout<<a<<" “;
sum_it_up(out,v,0,t,n);
for(auto a:mp)
{
for(auto it=a.begin();it!=a.end();it++)cout<<*it<<” ";
cout<<endl;
}
return 0;
}

1 Like