Subset Sum Easy no Test cases are getting accepted

#1

i did dry run of my code and build a recursion tree for it but can’t find the error in my code pls help me with this…

#2

Please share your code.

#3
#4

Please post your code here

#5

public class Main {
public static int Subsetsum(int[] arr,int vi,int sum) {
if (arr.length == vi && sum == 0) {
return 1;
}
if (arr.length == vi && sum != 0) {
return 0;
}
int fe = arr[vi];
vi++;
int two = Subsetsum(arr,vi, sum);
int one = Subsetsum(arr,vi, sum+fe);
return (one+two);
}

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int time = sc.nextInt();
	while (time != 0) {
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		int val = Subsetsum(arr, 0, 0);
		if (val > 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		time--;
	}
}

}

#6

To fix your code, you need to change a line.
Int one = Subsetsum(arr,vi,sum-fe);
As we now need lesser sum from remaining elements(since we included this element)
This will fix your code error.

Now in subset sum problem we usually need a sum value as well. Which in your case is 0 always. If it is intentional , then it’s fine . Otherwise change it in main() during call to function.

Thanks

#7

sum parameter represents the what we have added till now
so if we take eg of 1 2 3 at starting sum is 0 then in first recursion statement i made a call without adding first element and in 2nd recursion statement i added the first element to the sum that is 1 in this case…
(fe is first element )
if i make (sum-fe) then sum will become -negative how will this solve my issue

#8

this logic was also present in out hint video that is to add first element in one call and not add it in another call.

#9

In this way, your logic is correct. But the base condition is wrong.
Then in base condition,
If(sum == 0)…
You must check if(sum==k)…
Where k is the target sum of subset sum problem.

#10

0 is the target number in question.
question : Mike is a very passionate about sets. Lately, he is busy solving one of the problems on sets. He has to find whether if the sum of any of the non-empty subsets of the set A is zero.

#11

Are you getting TLE(Time limit exceeded) in every test case? if yes, then have you learnt dynamic programming?
This is a classical problem of dynamic programming.

#12

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.