Problem - Sum It Up (Backtrack)

#1

Hi I am trying to solve this problem but my code is printing same solution more than once and also output is not in non-ascending order. My code :
#include
using namespace std;
int t;
void printAll(int *a,int i,int j,int n,int *out)
{
int check=0;
for(int k=0;k<j;k++)
check = check + out[k];
if(check==t)
{
for(int k=0;k<j;k++)
cout<<out[k]<<" ";
cout<<endl;
return;
}
if(check>t)
return;
if(i==n)
return;
out[j] = a[i];
printAll(a,i+1,j+1,n,out);
printAll(a,i+1,j,n,out);
}
int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
cin>>t;
int out[n];
printAll(a,0,0,n,out);
return 0;
}

#2

Hello Gourav ,

  1. to maintain ascending order sort array in increasing order before calling printAll function.
  2. to avoid repetetion of same solution check if ur current element is already considered or not.
    regards
    Aman yadav
#3

for point 2 -> let say you want to include a[i] ,now before including check if a[i] is already there in out array or not if it is then don’t include else include.

for reference you can checkout this code - https://ide.codingblocks.com/s/172240

#4

if u r not getting above approach then follow this one

  1. from given array create an array having unique elements (u can use set or map to achieve this)
  2. now sort the new array in ascending order
  3. apply recursion on this newly sorted array to generate all subset and check whether the subset total sum is equal to t or not .if sum is equal to t then print all elements of that subset otherwise ignore that subset.

I hope u find this approach easy
regards
Aman yadav

#5

My new code, with this code I am passing few tests but still it is not correct

#6

can u please share the link.

#7
#8

Thanks I’ve passed all test cases :slight_smile:

1 Like
#9

glad to know that. please mark it resolved then.
tips
instead of using so many header files in your code just include
#include<bits/stdc++.h>
regards
Aman yadav

#10

@gourav hi gaurav please mark your doubt resolved