Trying for any one combination first

#1

#include
#include

using namespace std;

//problem: considering one number for only one combination

bool sum_it_up(vectorv, vectorans, int i, int sum, int k){

if(k>sum || i==v.size()){
	return false;
}

if(k==sum){
	//print the ans vector

	for(auto x:ans){
		cout<<x<<" ";
	}

	cout<<endl;

	//since we need all the combinations
	return true;
}


//recursive call for considering numbers

for(int number=i; number<v.size(); number++){

	//consider we can take this number and its ok
	ans.push_back(v[number]);

	bool sum_lies_ahead= sum_it_up(v,ans,number+1,sum,k+v[number]);

	if(sum_lies_ahead==true){
		return true;
	}

	ans.pop_back(); //backtrack,if not

}

return false;

}

int main(){

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	vector<int>v;

	int n;

	cin>>n;

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

		int no;
		cin>>no;
		v.push_back(no);

	}

	vector<int>ans;

	sum_it_up(v,ans,0,6,0);

return 0;

}

#2

You have added a wrong condition.

bool sum_lies_ahead= sum_it_up(v,ans,number+1,sum,k+v[number]);

if(sum_lies_ahead==true){
return true;
}

This condition is wrong inside for loop of recursive function.You have to print all combination.If you return true just after finding one combination then you will miss some of the combination.
In sample input:
1 1 6
1 2 5
1 7
out of three starting with 1 your function will print only 1.

#3

Also,you are not checking for duplicates.Like if you have array as {1,1,2,4}
and you want to find sum as 5
then you program will give output as:
{1,4} for first one
{1,4} for second one
You have to print unique combination only.For that you have to check if in current recusive call you have used that value or not.

#4

I have clearly stated in the title of the doubt- I am first trying to check for 1 combination only. (I’ll handle the duplicates and other combinations later on)
The error is: If the first element isn’t included in the combination it isn’t showing any combination.
Example
5
1 0 5 7 8
It is showing 1,5
whereas if
5
0 1 6 5 7
It isn’t showing anything

#6

@aman212yadav will you please check?

#7

bro i m not taking this doubt, some other TA is taking it

#8

Sorry bro! Tagged you by mistake in a habit of getting my doubts reviewed by you :neutral_face:

#9

You have added return true in the line of code that I have mentioned, you shouldn’t return from the function just after getting a single combination. Please make that change

Make the sum it up function as void ,in the first line just return,same for the subsequent line where you are printing comination and change rest code to the one below

//recursive call for considering numbers

for(int number=i; number<v.size(); number++){

//consider we can take this number and its ok
ans.push_back(v[number]);

sum_it_up(v,ans,number+1,sum,k+v[number]);



ans.pop_back(); //backtrack,if not

}

return;

#10

Please check it is still not working.
THIS WAS THE PROBLEM:
I am first trying to check for 1 combination only. (I’ll handle the duplicates and other combinations later on)
The error is: If the first element isn’t included in the combination it isn’t showing any combination.
Example
5
1 0 5 7 8
It is showing 1,5
whereas if
5
0 1 6 5 7
It isn’t showing anything