Subset Sum Easy

#1

#include

using namespace std;

bool is_subset(int *arr, int i, int n, int sum){

if(i==n){

	if(sum==0){
		return true;
	}

	else return false;

}

bool answ= is_subset(arr,i+1,n,sum+arr[i]);

bool answo= is_subset(arr,i+1,n,sum);

return answo or answ;

}

int main(){

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

	int n,t;

	cin>>t;

	while(t>0)
	{
		cin>>n;

	int arr[n];

	for(int i=0; i<n; i++){
		cin>>arr[i];
	}

	if(is_subset(arr,0,n,0)){
		cout<<"True";
	}

	else{
		cout<<"False";
	}

	t--;
}

return 0;

}

#2

I am getting a problem here while taking the subsets having the sum 0. In every case this code reaches a stage where it does not consider any element hence, the sum for that case will remain as 0. How to account for this case for sum=0; because otherwise every array will be shown to have a subset adding up to 0.

#3

to tackle this you can additionally add a parameter (bool taken) which is 0 initially!
whenever you consider any element(sum+arr[i]), you send 1 to taken, otherwise you send taken as it is for recursive calls.
At last if sum is 0, return taken.

1 Like
#4

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.