L10. Subset Sum I | Recursion | C++ | Java

[@takeUforward]

C++ Code: github.com/striver79/SDESheet/blob/main/SubsetSumsC%2B%2B Java Code: github.com/striver79/SDESheet/blob/main/SubsetSumsJava Instagram: instagram.com/striver_79/​

[@parthsalat]

Where's the link for the power set?

[@aasthachauhan4385]

can you please make a video on power set as you said?

[@aasthachauhan4385]

kzbin.info/www/bejne/mGikipWmgpqMqKc the link for powerset

[@takeUforward]

@@aasthachauhan4385 it is there

[@parthsalat]

@@aasthachauhan4385 Power set is very easy...spend some time on it and you yourself can develop an algorithm for it

[@lavanya_m01]

You have a lot of patience to trace out the whole recursion tree.. thanks a lot for this :)

[@debjitdutta17]

what else do you expect from a 6star coder,these nothing for him xD

[@rohanmishra2936]

humility is very rare these days though@@debjitdutta17

[@anushakulkarni8490]

The first recursion sum I solved on my own and got accepted in the first go....thank u so much !!

[@nahidfaraji5069]

Same goes with me. Hehhehe

[@nithish5296]

Same Broooooooooo !

[@MohanRam-mq2pk]

same!!

[@kumarsaurabhraj2538]

The time complexity of the recursive solution is also 2^N x N. We know that we will get 2^N subset sums and at last we sort the array so 2^N + (2^N)log(2^N) ~= 2^N x N

[@srikanthmathala940]

For simple variables (non-container types like int, float, etc.)(here it is sum), we don't need to adjust them explicitly after including them in a recursive call. The reason is each recursive call creates its own local variables, and any modifications we make within a recursive call are isolated and do not affect other recursive calls.

[@niyammuliya5787]

If we sort the array before passing in function func, then no need to sort sumSubset array by doing this, We have also reduced the time complexity from O ( 2^n + (2^n) log(2^n)) to O (2^n + n Log(n)).

[@venkateshn9884]

Yeah..but for that we we need to call right subtree before calling left subtree.

[@rakshankotian2737]

@@venkateshn9884 we need to sort in decreasing order in that case rit?

[@venkateshn9884]

@@rakshankotian2737 Exactly 💯

[@user-le6ts6ci7h]

You can't always do that , there could be chances , for certain test cases where the sorting order might go out of order Example [6,4,3,2]

[@amitranjan6998]

@@user-le6ts6ci7h Nooo ....it will also work ,if you sort at starting ,we can achieve using O (2^n + n Log(n)),no issue on this

[@amanbhadani8840]

The way you makes us understand each and every concept is just incredible bhaiya.For those finding it tough or not confident enough in recursion,i would suggest to solve more questions on trees.

[@growcodeyt7256]

The first recursive approach which I understood clearly.. Thank you so much sir.

[@imranimmu4714]

Couldn't Thank you enough Raj bhaiyya, I am currently going through Recursion playlist of yours, and I could absolutley say ,no one could have taught us better than this. Thank u soo much for your work.

[@VishalGupta-xw2rp]

I was able to grasp this as it's a kind of Subsequence but we are only concerned with its Sum..... To think i was able to think of a logic myself.... Wowww all thanx to you 🙏♥️🤩🔥

[@shivamshrey47]

If you just reverse the order of recursive calls (don't pick first and pick second), you would automatically get the resultant subset sum array in sorted form. This way one can avoid the final sorting of the result.

[@pavanpatel6877]

Woahh...That's a good observation though. Thanks shivam!

[@26.aniketmatkar20]

No it will not work, it will just reverse the answer vector. One element i.e 4 will remain unsorted

[@subham8746]

No it'll only reverse the output, it won't be sorted.

[@Siscerto]

@@26.aniketmatkar20 bruh,,, it literally passed,,, and its sorted... idk how its getting sorted tho.. gotta draw recursive tree... however they never asked for sorted output tho ArrayList subsetSums(ArrayList arr, int N){ // code here ArrayList sol = new ArrayList(); setsum(sol,arr,N,0,0); return sol; } void setsum(ArrayList sol, ArrayList arr, int N, int i, int sum){ if(i==N){ sol.add(sum); return; } // 1.skip ele and proceed setsum(sol,arr,N,i+1,sum); // 2.pick ele, add sum and proceed setsum(sol,arr,N,i+1,sum+arr.get(i)); }

[@Siscerto]

The thing is we dont need to SORT, they're sorting it in the DRIVER code

[@Rajesh-op8zx]

Actually we dont need to sort because if you first call for not pick then pick we get subset sum in ascending order thus T.C= O(2^N) . Code that is submited without sorting : void fun(int index, int sum , vector &arr,int N,vector &ans) { if(index==N) { ans.push_back(sum); return; } fun(index+1,sum,arr,N,ans); fun(index+1,sum+arr[index],arr,N,ans); } vector subsetSums(vector arr, int N) { vector ans; fun(0,0,arr,N,ans); return ans; }

[@tanyagupta1176]

Hey , can you explain why we are not subtracting arr[i] from sum when backtracking in case of not take.

[@tanyagupta1176]

@22.37

[@stepup7052]

@@tanyagupta1176 beacuse we dont add it we just skip that index in parameter

[@mriduljain1981]

we can reduce the time for sorting by modifying the code as below - void solve(vector arr,int i,vector &ans,int sum){ if(i == arr.size()){ ans.push_back(sum); return; } solve(arr,i+1,ans,sum); sum = sum + arr[i]; solve(arr,i+1,ans,sum); } vector subsetSums(vector arr, int N) { vector ans; solve(arr,0,ans,0); return ans; }

[@tanujabetha5400]

Just a doubt in the code: When you are doing sum + arr[i], that means you are picking that element right. When you do to not pick recursion, dont you have to do sum = sum - arr[i] and then call recursion.

[@princerajput6709]

I have made this question from myself using both iterative and recursive approach thanks striver from bottom of my heart ❤

[@anishkarthik4309]

We just need to sort the initial array(n logn) , and do not pick and then pick. So we end up getting an array of sums in sorting order(2^n for generating) T.c = O(n logn + 2^n) = O(2^n) S.c = O(2^n)

[@idiot3641]

it wont't work

[@yashlad875]

@take U forward Thanks for the amazing recursion and dynamic programming series, For this question I think we can have TC = 2^N by sorting the given array first and deciding to not pick before picking. That way the resultant array will be in sorted order!

[@mridulshroff824]

Can you explain how not picking before picking reduces TC? I couldn't understand.

[@shiyadh4471]

@@mridulshroff824 Because we need to reach to the lower sums before reaching to higher sum values.For example, take [ 2, 5, 1] as the arr.We sort it to [ 1, 2, 5] why? bcz, we will go and find all possible subsets starting with 1 ,then with 2 then only 5 - thus they will be in ascending order.Now, lets say you have slected [1,2] and the recursion call is suppose to pick/not pick the element 5 , by not picking it, my sum is 1+2=3 but by picking its 1+2+5=8 . so, which call i should make to get the least sum first(ascending order) ? Its the not pick case right ...

[@shashankdixit92]

I think if we select not picking first, then in the Array (1,2,3) 3 would be picked up first...

[@yashlad875]

@@mridulshroff824 Because then we don't need to sort the output array in the end.

[@yuvrajluhach5665]

Moving to L11 , this was an easy one 👍

[@mountINEER]

solved this under a minute, really quality content , best way to give back your learnings, true guru !!! . Eagerly waiting to meet you one day and I surely will ..

[@s.g.prajapati3597]

First Viewer, just wanted to say, You're doing amazing job! Keep up the good work!

[@ganapatibiswas5858]

We can sort the input array and then do recursion such a way that we take smallest elements first. This will generate subset sum smallest to largest and we don't need to sort the final array at the end.

[@your_name96]

umm, so you are adding code/logic complexity with no improvement in time complexity ?

[@ganapatibiswas5858]

@@your_name96 no we don't need to sort the final array which has the size of 2^n. We sort the input array which has size n. So time complexity will be less.

[@your_name96]

@@ganapatibiswas5858 oh yes,will try to implement this one

[@codediary2568]

he is a legend for the first time I have solved a recursion question myself

[@shreyxnsh.14]

Thnaks striver, did all that by myself by just seeing half the approach.

[@yogeshvaishnav6464]

You said TC of recursive solution is 2^N + 2^N log (2^N), isn't it equal to 2^N + N*2^n(log 2) = N*2^N + 2^N = O(N * 2^N) same as iterative one?

[@deanwinchester8691]

yes you're right.

[@democratcobra]

Thanks a lot for adding the visualization of the RECURSIVE CALL, it really helps in getting the proper understanding. Thanks a lot for your effort and hardwrork. Really Helpful.After watching this i am going to be member of your chanel.Really well explained.

[@shashwatpandey8243]

instead of sorting the array with subsets sum, we can just sort the array which contains n elements. and then we have to first call the function in which we do not include current element in the sum. this will result in sorted result only. and also sorting time would be reduced

[@saddy4420]

Same this will reduce the TC from 2n log 2n to n log n

[@namansharma7328]

📢🔥🔥What is the space complexity?????? Is it O(N) cuz at max there would be N revursive call waiting in the stack. (there are n+1 levels in the stack space tree). Plz clarify

[@ankittjindal]

ye qsn sbse easy tha phle k 2-3 lectures me qsns ko 2-3 bar rewind krke dekhna pdh rha tha lekin isme niii thnx😃

[@funnythings8603]

why sum is not minus when we came back and go to not pick option?

[@Bharat_Rider]

Understood bro i just understood the method without pseudo code and wrote program myself. Great explanation

[@utkarshsarin9443]

Thank you so much Bhaiya...I am starting to get a better idea of recursive calls know and I am say this with a 100% certainity that your videos have a major role in all this ❤

[@paulbarsha1740]

understood sir, but why we are sorting it again in the main function? i saw this in the documentation of this problem int main() { vector < int > arr{3,1,2}; Solution ob; vector < int > ans = ob.subsetSums(arr, arr.size()); sort(ans.begin(), ans.end()); cout

[@atharvakulkarni2024]

BHAIYYA PLEASE EK REQUEST HAI EK VIDEO ISPE BHI BANAO DEPTH ME KI HUM POP BACK KAB KARTE HAI BACKTRACK KE TIME USME BOHOT CONFUSION HO RAHA HAI

[@akshaykenjale2642]

So basically how we can differentiate between subsequence and subset, subsequence can be like which follows order of array, but then too need some more points

[@tasneemayham974]

STRIVERR!! I watched the first couple of minutes of your video and then was able to code the solution alone!!! Thank you for the amazing content!!!!!!

[@Suryansh_Goel.]

sorting the given array in decreasing order and doing not pick before pick will reduce the time complexity a little as the final answer will not need sorting

[@AmanKumar-dl8os]

we can remove the time complexity of sorting the solution by making the right sub-tree to the left and the left sub-tree to the right. Please try it once, this means swapping the recursive function calls.

[@chetanguduru]

I have done using this method. Does this have any down side? There is no requirement of sorting here vector subsetSums(vector arr, int N) { if(N == 0) { vector ans; ans.push_back(0); return ans; } vector output = subsetSums(arr,N-1); int size = output.size(); for(int i=0;i

[@Anjaliojha-o2l]

agar hmlog given array ko phle hi sort kr de decreasing order me aur not pick wala function call pick wale function call k phle rkh de, to hme apne ans ko alag se sort krne ki jarurat nahi pdegi, and aise hm 2^n*log(2^n) T.C ko n*logn se optimise kr skte h.

[@artifice_abhi]

Bhaiya mtlb kaise btaun apne to kamal kardia ye question mne khud try kia aur first attempt m kardia Apse padhkar maza agya.

[@Bharat_Rider]

If someone does this tracing for merge sort till the end his confidence increases a lot in recursion

[@alexquistain4509]

Best explanation i have found here in this video thanks a lot for ur hard work nd keep doing

[@daksh8055]

I have a doubt that when do we make the helper function return something and when do we not return anything, would it be possible if in this solution the 'func' functions return the final arraylist?

[@shashankpandey6230]

instead of storing it in arraylist we can use treeset to reduce the extra overhead of sorting the list

[@vishious14]

TreeSet would still take logN time to insert each sum. So for n subsets sum it'll take n*logn time, which is same as sorting the final container.

[@roushanraj8530]

thank you bhaiya, for your awesome informative videos of most important DSA question, aap jldi thik ho jao ......

[@sonalisinha325]

why have you not used sum = sum-arr[index] before 19 statement

[@lakshsinghania]

thnks bhaiya i was able to do combination sum 3 on my own only because of u

[@aravindben6254]

The below code avoids sorting and has O(2^n) time complexity instead of O(2^n)+O(2^n log(2^n)) void comb(vector &sums, vector &arr, int i, int n, int sum){ if(i>=n){ sums.emplace_back(sum); return; } comb(sums,arr,i+1,n,sum); comb(sums,arr,i+1,n,sum+arr[i]); } vector subsetSums(vector arr, int N) { // Write Your Code here vector sums; comb(sums,arr,0,N,0); return sums; }

[@ompandey8470]

congratulations bhaiya apka google me hogya na!, Main bhi aa rha hu jldi hi milte hai

[@HarshitMaurya]

looking at these combination problam at saying abhi to ye sb bhaiya ye padhaya subsequences me tha and then i tried myself and got ac , best feeling ever

[@VY-zt3ph]

The space complexity here will be of O(N) because that will be the depth of the recurs ion tree.

[@ankursingh8296]

Sort array in reverse order and do not take first and next call for take this way we get sum in inc order automatically..I am assuming all elts to be distinct..tc 2^n and SC is 2^n

[@abhisheksa6635]

Because of the earlier videos and ruminating in my sleep, I could solve this, honestly I did one mistake that is keeping a vector storing the subset, should have saved a sum variable.

[@mohitkumarbansal3486]

I really afraid of this questions but when I see your video some magic happen

[@gepliprl8558]

Thank you for using real english. I subscribe your soul 👍

[@saketjaiswalSJ]

//sum of subsets in sorted order //t.c is for every index i have two choice pick and not pick for example i have 3 indxes the i will //have total 6 choices p/np for each indexs hence for n indexes i will have 2^n choicess //also there is extra 2^n*log(2^n) t.c for sorting the ans array hence total t.c is (2^n * 2^n *log(2^n)) class Solution { public: void solve(vector &a, int index,int s,int N,vector &ans) { if(index==N) { ans.push_back(s); return; } //picking element from the index solve(a,index+1,s+a[index],N,ans); // s=s-a[index];aisa kuch nhi hoga s datastructure nhi hai //s ek simple variable hai samjha kuch nhi krna hai //decreasing the sum //simple backtrack //pick notpick ka function easily call ho jayega samjha be solve(a,index+1,s,N,ans); } public: vector subsetSums(vector a, int N) { vectorans; int index=0; int s=0; solve(a,index,s,N,ans); sort(ans.begin(),ans.end() ); return ans; } };

[@akshatjain3484]

one of the best explanation!!!!!!!!

[@fivexx469]

do we even need to sort the array ,as it is not asked in the question?

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@madhurgupta3849]

I think It can be done in single recursive call. vector subset(vector &num,int i) { // Write your code here. vector ans; if(i==num.size()){ ans.push_back(0); return ans; } ans = subset(num,i+1); int size=ans.size(); for(int j=0;j

[@ishanmoykhede9484]

solved in 8 min just by reading problem statement ❤‍🔥❤‍🔥❤‍🔥

[@ankityadav6914]

I do think so that the time complexity of this approach would be O(2^nlog(2^n)) = O(n* 2^n). Please have a look at my code below, it is accepted on gfg and I think it is having time complexity O(2^n) only, please correct me I am wrong. The idea is still similar to either pick an element or not pick the element but we are only pushing sum+arr[n-1] value into the vector. Also, the recursive function will not consider of the case when no element is picked hence we have to push_back(0) into the vector at the very beginning. void subSum(vector &arr, int n, int sum, vector &s) { if(n == 0) { return; } s.push_back(sum+arr[n-1]); subSum(arr, n-1, sum, s); subSum(arr, n-1, sum+arr[n-1], s); } vector subsetSums(vector arr, int N) { vector s; s.push_back(0); subSum(arr, N, 0, s); return s; }

[@armed3719]

why r we not removing here like we did in other problems

[@pirangitharun8736]

Can be done in 3 ways [Bit manipulation, DP, Recursion]

[@takeUforward]

Dp wont be possible as you need to print sums so you need to go to the depth always.

[@pirangitharun8736]

​@@takeUforward Thanks for the mention bro

[@siddhartharathour1802]

if we call the function that does not include first element in current sum and then call second function. then we will get subset sum in sorted order than there is not need to sort. public void ss(ArrayList arr, int n,int sum,ArrayList sub){ // code here if(n==arr.size()) { sub.add(sum); return ; } ss(arr,n+1,sum,sub); ss(arr,n+1,sum+arr.get(n),sub); }

[@venkythesmart440]

you are doing amazing job ! keep up good work!

[@chiragarora870]

Sorting isn't required, driver code is automatically sorting our array

[@aftabansari3845]

Submitted successfully w/o sorting the result array.

[@vyankateshkulkarni4374]

Thanks striver. you made understanding so easy. thanks brother

[@a.yashwanth]

Without sorting also all testcases passed for me in GFG.

[@naveenkumars1856]

i have an good resume sir ., i find no ways to join Directi for SDE

[@thexhist3609]

whats the difference between recursion of subsequence and subset , isn't both of them same

[@Sarkar.editsz]

Thanks a lot , i did this question all by myself becoz of your videos and your guidance , thanks a lot

[@dewanandkumar8589]

Understood

[@prabhakaran5542]

Understood ❤

[@amityadav-km5rx]

Very Nice Lecture

[@leo-x1d1f]

best think of striver bhaiyya videos is promotion tell (time) so we can skip promotion easily every youtuber have to do this

[@aysams2]

In the recursive fxn, why is the condition if( ind == N) and why not if( ind == N-1) as we're using 0 base indexing ???

[@Lullurluli]

It is zero based indexing but on function call we are incrementing ind + 1 so it will return as n == ind

[@jha.brajesh]

2:20 GFG edited their expected space complexity

[@anirudhsoni6001]

Thanks for the video. What if question is twisted a little bit and we have to find the smallest subset sum value which cannot be formed? Ty!

[@thegreekgoat98]

That's a good question

[@TheElevatedGuy]

can we store ans in a multiset and covert to vector and return. By the way thank you very mush for this playlist.

[@apoorvgupta1211]

Hey Striver, Big fan and thank you for the amazing series, but in this question, we are asked about subsets and what you have explained is the solution for subsequences. In your video on subsequences, you had explained the difference between subsets and subsequences - "Subsequences can be contiguous as well as non-contiguous but subsets are always contiguous". This point can also be observed if we go to the problem link and see the examples mentioned.

[@kaichang8186]

understood, thanks for the perfect explanation

[@GeneralistDev]

void dfs(vector &nums,vector &ans,int idx, int sum){ if(idx>=nums.size()){ ans.emplace_back(sum); return; } // take dfs(nums,ans,idx+1,sum+nums[idx]); // not take dfs(nums,ans,idx+1,sum); } public: vector subsetSums(vector arr, int N) { vector ans; dfs(arr,ans,0,0); return ans; }

[@parthsalat]

Where's the link for the power set?

[@anubhabpaul7160]

Can anybody tell.. why we r not doing sum-arr[i] when we r returning... so the previous sum dont add... as we do in other subset problem

[@CodeRocks-z6g]

we are passing sum+arr[i] directly so when recursion return and goes to not take f(ind,sum) sum is passed not sum+arr[ind]

[@chennurugurusankar2955]

We should not consider input and output in space complexity right then space complexity will be O(N)

[@roliagrawal3124]

Just one confirmation i need incase of list we remove last element and incase of variable we just return it. It happens because of pass by value and pass by reference?

[@neyovyas3992]

Please try to upload video daily and love your videos and explanation too much

[@shivamsrivastava1017]

Are we allowed to return same sum multiple times in the array if sum of different subsets is the same

[@rpriyanka28]

he is the definition of handsome with brains!!

[@ankushladani496]

I think code is written wrong Because we have to backtrack also So sum should be subtracted before another recursive call

[@udiiiiiit5020]

We pass sum+arr[i] to next function call when picking the current element and do not change the value of sum itself, so when going for not picking recursive call we just pass sum.

[@atulpardhi9499]

bhaiya sheet ke only 180 question ki practice se interview crack ho skta hai kya. my 3rd year is going to end and in have not prepared yet? plz help bhaiya.

[@akshayrathod7679]

Dont worry u have time

[@RoushanKumar-dp2qq]

I guess Time Complexity can be reduced significantly!! Instead of sorting the result array of size of size 2^n we can sort the input array of size of size n. And while picking instead of pick, FIRST perform NOT pick THEN pick class Solution{ ArrayList subsetSums(ArrayList arr, int N){ Collections.sort(arr); ArrayList result = new ArrayList(); subsetSums(0, 0, arr, result); return result; } void subsetSums(int i, int currSum, ArrayList arr, ArrayList result) { if(i == arr.size()) { result.add(currSum); return; } //not pick ith element for sum subsetSums(i+1, currSum, arr, result); //pick ith element for sum subsetSums(i+1, currSum+arr.get(i), arr, result); } }

[@nileshchandra6435]

Not really. for [1,2,3]. the subset sum for [3] will occur before [1]. So, the final answer would still be unsorted.

[@RoushanKumar-dp2qq]

@@nileshchandra6435 can u please elaborate your point, as the code above passes all the test cases on GFG including [1,2,3] (as first I am performing NOT pick then PICK)

[@shyamaprasadmohanty6215]

Note: You don't need to explicitly backtrack here because the recursive stack itself takes care of the variable sum's state!

[@ritikshandilya7075]

Thankyou so much for great content Striver

[@vikramjha4]

Can't thank you enough for these videos!

[@kirthe1116]

When to use pick/nopick method and when to use strategy mentioned in previous vide is confusing. Can someone clarify

[@amitrawat8879]

you can use different methods according to the constraints given in the question. like if the constraint for time complexity is 2^n then you can use recurrsion, other can use other optimal solutions.

[@NamasteJi-c1v]

May be I am not able to understand the logic properly but to the extent that I understand I had one doubt when we don't pick any index then our sum is 0, and when we move to left of that than also our sum will be 0 so what I am trying to say is that we should be having duplicate values, can some one help me and let me know, if I am missing something

[@mayankjaiswal1492]

man, this is a banger, thank you so much for this

[@parthsalat]

C++ code at 23:50 Complexity analysis at 20:05

[@nirmalkishore9226]

what is the difference between subsequence and subsets?