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

[@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.

[@growcodeyt7256]

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

[@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 🙏♥️🤩🔥

[@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.

[@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

[@yuvrajluhach5665]

Moving to L11 , this was an easy one 👍

[@princerajput6709]

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

[@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.

[@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

[@s.g.prajapati3597]

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

[@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 ..

[@codediary2568]

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

[@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

[@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😃

[@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.

[@shreyxnsh.14]

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

[@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!!!!!!

[@Bharat_Rider]

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

[@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.

[@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 ❤

[@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

[@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.

[@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

[@chad._life]

class Solution { public: void subset_sum(int ind,vectorarr,vector&ans,int sum,int n){ if(ind==n){ ans.push_back(sum); return; } // case to pick an element to be added in sum subset_sum(ind+1,arr,ans,sum+arr[ind],n); subset_sum(ind+1,arr,ans,sum,n); } vector subsetSums(vector arr, int n) { vectorans; int sum =0; int ind =0; subset_sum(ind,arr,ans,sum,n); return ans; } };

[@alexquistain4509]

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

[@ompandey8470]

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

[@Bharat_Rider]

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

[@roushanraj8530]

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

[@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

[@gepliprl8558]

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

[@mohitkumarbansal3486]

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

[@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

[@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.

[@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

[@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.

[@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

[@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; }

[@akshatjain3484]

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

[@lakshsinghania]

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

[@ishanmoykhede9484]

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

[@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

[@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

[@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.

[@Taal_Magic]

It can be done without sorting if we do not pick first and the call the pick recursion call.

[@ranasauravsingh]

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

[@VY-zt3ph]

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

[@khushichaudhary4859]

22:24 c++ code

[@chiragarora870]

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

[@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; }

[@leo-x1d1f]

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

[@rpriyanka28]

he is the definition of handsome with brains!!

[@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; } };

[@venkythesmart440]

you are doing amazing job ! keep up good work!

[@abhishek_Gupta25]

class sol { public : void func(int index,int sum,vector&arr,int n,vector&sumset) { if(ind==n) { sumset.push_back(sum); return; } // pick func(index+1,sum+arr[index],arr,n,sumset) // not pick (sum not update) func(index+1,sum,arr,n,sumset); } public : vector sumset(vector arr,int n) { vector sumset; func(0,0,arr,n,sumset); sort(sumset.begin(),sumset.end()); return sumset; } };

[@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.

[@aftabansari3845]

Submitted successfully w/o sorting the result array.

[@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

[@vyankateshkulkarni4374]

Thanks striver. you made understanding so easy. thanks brother

[@parthsalat]

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

[@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.

[@amityadav-km5rx]

Very Nice Lecture

[@Sarkar.editsz]

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

[@kaichang8186]

understood, thanks for the perfect explanation

[@jha.brajesh]

2:20 GFG edited their expected space complexity

[@mihirsharma2338]

Python Code ... class Solution: def solve(self, ind, arr, sum,ans): if ind== len(arr): ans.append(sum) return self.solve(ind+1,arr, sum,ans) self.solve(ind+1,arr, sum+arr[ind],ans) def subsetSums(self, arr, N): # code here ind,sum = 0,0 ans = [] self.solve(ind,arr,sum,ans) return ans

[@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

[@ritikshandilya7075]

Thankyou so much for great content Striver

[@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

[@vikramjha4]

Can't thank you enough for these videos!

[@neyovyas3992]

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

[@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); }

[@chowmein1397]

Link for Power set Video mentioned at 3:15 : kzbin.info/www/bejne/mGikipWmgpqMqKc

[@a.yashwanth]

Without sorting also all testcases passed for me in GFG.

[@prabhakaran5542]

Understood ❤

[@shyamaprasadmohanty6215]

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

[@mayankjaiswal1492]

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

[@RV-qf1iz]

Here is the Java Code for Reference ArrayList subsetSums(ArrayList arr, int N){ ArrayListl=new ArrayList(); backtrack(l,arr,N,0,0); return l; } public static void backtrack(ArrayListl,ArrayListarr,int n ,int i,int sum){ if(i==n){ l.add(sum); return; } backtrack(l,arr,n,i+1,sum); backtrack(l,arr,n,i+1,sum+arr.get(i)); }

[@shatadal_das]

C++ class Solution { void func(vector arr, int N, vector &sums, int sum = 0, int i = 0) { if(i >= N) { sums.push_back(sum); return; } func(arr, N, sums, sum, i + 1); sum += arr[i]; func(arr, N, sums, sum, i + 1); } public: vector subsetSums(vector arr, int N) { vector sums; func(arr, N, sums); sort(sums.begin(), sums.end()); return sums; } }; It's my solution, before watching Striver's solution.😁

[@UECAshutoshKumar]

Thank you sir

[@funnythings8603]

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

[@v.sreesairam9488]

Just wow bhaiya thank you very much:)

[@yashstudio7396]

Same as subsequences sum❤

[@dheerajnahariya9494]

Good to see you after long time bhaiya

[@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

[@sonalisinha325]

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

[@chennurugurusankar2955]

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

[@ankushladani496]

Thanks Bhaiya

[@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)

[@harshbardhanon4901]

Here why we are not subtracting the sum while backtracking

[@takeUforward]

Because we passed in the params!

[@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

[@jaskiratsinghosahan4638]

Crisp clear explanation 👍

[@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?

[@amityadav-km5rx]

NIce lecture.

[@vashishthsharma4411]

thank you bhaiya 😇😇😇😇