Target Sum Subsets - Solution | Recursion | Data Structures and Algorithms in JAVA

[@sakshamkashyap7329]

If Anyone Stuck in this ques with submission in Pep Portal : Simply use this, in starting of function if(sos > tar) return;

[@tapans2998]

thanks bhai

[@rahulphutela9174]

@Anugrah Johnson This condition is used to stop unnecessary Recursion calls. Please see below the working code: public static void printTargetSumSubsets(int[] arr, int idx, String set, int sos, int tar) { if(sos>tar) return ; if(idx == arr.length){ if(sos == tar){ set = set + "."; System.out.println(set); } return; } printTargetSumSubsets(arr, idx+1, set+arr[idx]+", ", sos+arr[idx], tar); printTargetSumSubsets(arr, idx+1, set, sos, tar); }

[@geetanegi2736]

@@rahulphutela9174 thank u bro😬

[@bentennyson8923]

@Anugrah Johnson for reducing time (avoiding TLE exception), and even if you continue there is not a solution as sos>tar

[@ankitbhardwaj7363]

Won't work if there are negative value(s) in array.

[@ritikshandilya7075]

literally amazing !! recursion beginners folks can learn a lot from this video

[@GauravKawatrakir]

If we able to saw the memory stack with recursion, its become more clear understanding.

[@tarunkumar3279]

Great man with a great solution and with a great initiative. All the best sir.

[@pawanagrawal7653]

instead of passing the idx pointer in the function , can we run a for loop from i=0 to n-1 and call the recursive the call from inside the for loop, and each time checking the base case if , sum==target or not , if sum==target print ans , and if sum>target then return ; .

[@aashishgoyal1436]

Thank u so much sir for solving different type of problems

[@Pepcoding]

All the best

[@AshishBaranwal-dl7fi]

Sir, we can also optimize it using a if condition before recursion calls, if(sos > target) return;

[@himanshudewan6535]

if(sos > tar){ return; } Agar in future negative values hui tho we then cant find it

[@avinashvikramjha3343]

Very nice and informative..Thanku soooo much

[@Pepcoding]

So nice of you

[@Elon-musk-007]

sirji ek condition forget kar gye aap-----> if(sos>tar)return;

[@Pepcoding]

Agreed.

[@RajChahalNsit]

very easy to understand explanation ... thanks.. .

[@sasidharnaidu4507]

Sir, why calculate the target sum at every call? Simply calculate the sum of final subsets in the base case. That way, we can reduce some calculation

[@sagargarg4910]

hello sir, i have tried the problem this way public static void printTargetSumSubsets(int[] arr, int startIndex, String set, int sum) { //special case if(sum == 0) { System.out.print(set+". "); return; } //base case if(startIndex == arr.length) { return; } if(sum < 0) { return; } printTargetSumSubsets(arr, startIndex+1, set+""+arr[startIndex]+", ", sum-arr[startIndex]); printTargetSumSubsets(arr, startIndex+1, set, sum); } here I am printing and returning when I counter the subset i.e sum becomes zero, it's slightly different than your code but I think the approach is the same. while submitting, it couldn't pass one test case and I can't think the test case on which the approach is not working. can you please help me understand what could go wrong

[@sakshiaggarwal6199]

Thank you so much sir!!

[@gyandyan]

#include using namespace std; // set is the subset // sos is sum of subset // tar is target void printTargetSumSubsets(vector arr, int idx, string set, int tar) { //write your code here if(tar==0){ coutn; for(int i=0;i>arr[i]; } cin>>tar; printTargetSumSubsets(arr,k,set,tar); return 0; }

[@ShubhamSahu-fe8ed]

BEST 👏👏👏

[@Pepcoding]

Keep learning. For better experience, visit nados.io, where you will get well curated content and career opportunities.

[@nikhiljain3011]

I want tio know , if backtracking questions are also being covered by sumit sir ? Please confirm someone

[@amandixit3555]

sir jaise aap har recursion mei arr pass kar wa rahen hain , par tree mei har level par ek kam karte jaa rahe ho element , iska matlab har level par woh no. upar qtn mei bhi hoga aur neeche ans mei bhi, par hum convenience ke liye show nahi kar rahe hain upar ? sahi soch hai sir kya ?

[@Pepcoding]

hnjii beta

[@mukultaneja8014]

Is subset equal to subsequence ? If not then if the sum we need is 30 , can we print 10 20 and 20 10 because both are subsets but latter is not subsequence ( does not maintain order )

[@Pepcoding]

I use the two terms in same manner. Subset is to array as subsequence is to string.

[@umangchhabra9678]

sir 1 testcase is giving TLE.

[@Pepcoding]

kahan pe?

[@umangchhabra9678]

@@Pepcoding pepcoding editor

[@akshatpandey2609]

Sir n=27 pass kiya gaya hai

[@RaviKumar-kr]

include this base condition at top it will optimize the code if(sos>tar){ return;} and you will pass that test case of n=27.

[@raghavbansal9020]

Hello sir, v nice video. I tried solving it by myself. But, wrong answer. What's the issue sir, can u please have a look. It will be of much help. public static void printTargetSumSubsets(int[] arr, int idx, String set, int sos, int tar) { if (sos == tar){ System.out.println(set+"."); return; } if (sos > tar || idx >= arr.length){ return; } for (int i = idx; i < arr.length ; i++){ printTargetSumSubsets(arr, i+1, set+arr[i]+", ", sos + arr[i], tar); } }

[@SCRIPTSAG]

Thank sir

[@Pepcoding]

Glad you liked it!! share as much you can

[@ankurtiwari5534]

Sir agar if ka condition true ho jaye to return to terminate kar dega pure function niche wala recursion to use hi nahi ho payega

[@Pepcoding]

For better insight, visit nados.io, post your doubts, community will help you out there.

[@anirudhpanwar7142]

Why didn't you use the frame work for recursion that you were using in the beginning ?

[@sriramkrishnamurthy5528]

Because these problems are about making choices and these type of questions are void recursion based questions where we explore multiple choices . In the beginning we solved questions which were not void recursion and they were questions which relied on the recursive solution for a smaller input for building a an output for a bigger input, those were faith-expectation problems and these are exhaustive choice exploration problems (backtracking) hence the same framework used in the earlier problems isn't used in these types of problems as these are predominantly two different types of recursive problems !!!!!!! Cheers bro ! 🔥👍

[@dajindersingh9538]

Sir, that one test case is still not resolved.

[@Pepcoding]

Try it now

[@AryanSharma-dh4fb]

this is subsequence not subset , right ?

[@gauravgupta9477]

Is there any trick to identify quickly if there exists overlapping subproblems??

[@Pepcoding]

Recursion tree mei parameters ko dekho. Kahin same hain?

[@manavmalhotra8513]

target sum subsets using backtracking , vo kha hai?

[@ankurtiwari5534]

Wahi samajh nahi aa raha hai sir

[@waez2120]

if idx==len(arr): return if sos==tar: print(asf,'.') return and if idx==len(arr): if sos==tar: print(asf,'.') return else: return 1st Base is giving me incomplete answer. Can Someone explain me why?

[@varunmodi5608]

It is because when idx==len(arr), i.e., the last element is included and the sum has been reached. Your code is not accounting for that inclusion. In which case, you will have the correct answer, but on the position len(arr). The program just returns without ever checking if sos==tar. It thinks "one condition fulfilled, return". It has to check for the second condition as well. Hence the second if inside the first one. Hope you understand. Cheers mate.

[@rolitiwari7527]

sir I am not understand line no 28 or 29 code plzz explain the code

[@Pepcoding]

For clearing such doubts you are most welcome on nados.pepcoding.com

[@riaria5982]

Dear Sir/All viewers, I have one question regarding the base case- why we haven't checked the base case like below: if(idx < arr.length) { if(sos==target) { System.out.println(set + "."); return; } } OR, we can do smart recursive call and lazy base case like below: if(sos==tar) { System.out.println(set + "."); return; } if(idx

[@Pepcoding]

Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding. Also, we have a premium facility available for the students in which you can get the 12 hours doubt support facility. Jisme aap agr kisi bhi question main kahin bhi faste ho to aap doubt support par reach kar skte ho aur aapko TA assign ho jayega and you can get your doubt resolved from them.

[@gyandyan]

u r correct bro, we can also do same as u mention above

[@kartiksood8277]

public static void printTargetSumSubsets(int[] arr, int idx, String set, int sos, int tar) { if(sos == tar){ System.out.println(set + "."); return; }else if(idx == arr.length || sos>tar){ return; } printTargetSumSubsets(arr,idx+1, set + arr[idx] + ", ",sos + arr[idx], tar ); printTargetSumSubsets(arr,idx+1, set,sos , tar ); } I used this logic. It is failing one test case.

[@Pepcoding]

for such queries visit on to nados.pepcoding.com and post your query on community tab.

[@divyaanshP]

#include #include using namespace std; void printTar(vector& coin, int tar, string asf, int idx){ if(tar == 0){ cout

[@rishabhgoyal2835]

sir hume sub-set nikalne the , lekin apne recursion sub sequence ka kia hai........... ab agar kisi din aise subsequence generate hogya ( jo non-continuous ho) or vo target ke barabar hogya ...to hum to print krdege ...... lekin ques me to subset ( must be continuous) manga hai.... what to do ?? confused ..!!!!!!!!!!!!!! @pepcoding

[@Pepcoding]

beta subset aur subsequence same hota hai, non-continuous bhi ho sakta hai. subarray continuous hota hai.

[@rishabhgoyal2835]

@@Pepcoding thank you sir .. got it now !!! bhot pyaaara samajate ho aap

[@anjneykumarsingh4461]

Fhinish!

[@Pepcoding]

great