Subset sum easy problem-1

#1

here is my code:https://ide.codingblocks.com/s/61746
here i am facing the problem of base case code.In the code above , it is true for all cases except one i.e., when exclude all elements in the array,sum is still 0,it must return false.but it returns true according to my code. i am unable to find a way to solve the test case.I just want a better base case that can solve all the test cases.

#2

Hii Pulkit,
Send the sum as -1 when you call getss function and in base condition first check whether a == A.lenght if yes, then check whether sum is 0 or not, if sum is 0 then return true else false

#3

sir it is not working as

  1. in s i am storing the sum.so i cant pass value of sum as -1.
  2. the main problem with code is that in one of the test case in which i exclude every element sum is still 0 and a==A.length. so it must return false in this particular testcase
#4

Hii pulkit,
In that case pass sum as Integer.MIN_VALUE in getss function and in getss function check is sum is equal to Integer.MIN_VALUE then initalize sum with array element at that index. This will solve your problem as if you exclude all elements then sum will not be equal to 0 and in any case sum of all elements can’t be equal to infinity

#5

sir, it would be very kind of you if you can make the changes in the code for my better understandability.
Thanks sir.

#6

Hii Pulkit,
I have made changes in your code and you can see them in the following link:
https://ide.codingblocks.com/s/62048

1 Like
#7

thanks bro for solving the problem

#8

please check my code , i am getting WA.
import java.util.*;
public class Main {
static boolean subset(int arr[], int idx, int sum , int count){
if(count==0&&idx==arr.length)
return false;
if(idx==arr.length&&sum==0&&count>0){
return true;
}
if(idx==arr.length&&sum!=0)
return false;

	boolean sc=subset(arr,idx+1,sum,count);
	boolean fc=subset(arr,idx+1,sum+arr[idx],count+1);
	
//	System.out.println(fc+" "+sc+" "+idx);
	return fc||sc;


}
public static void main(String args[]) {
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t-->0){
		int n=sc.nextInt();
		int arr[]=new int[n];
		if(subset(arr,0,0,0))
		System.out.println("Yes");
		else{
			System.out.println("No");
		}
	}

}

}