Ep14- Combination Sum 3 | Medium level Recursion Problem | DSA | Codes available in description

[@arghya_0802]

Summary: 1. Today's question is the culmination of Combination Sum-I and Combination Sum-II 2. Instead of having a given vector nums or arr, we are asked to consider numbers from 1 to 9(both inclusive) 3. We can also visualise them to be inside an array but actually we don't to create it and use extra space. 4. Now we need to pass in the void help() the following parameters: 1) i for the element and n for the target sum 2) sumTillNow to calculate the sum we have accumulated till now 3) k for the number of elements we require in our subset 4) vector subset and vector ans 5. Now we will have the base conditions: a) if(k==0) It means we have calculated the number of elements required. Thus check whether sumTillNow== n. If so include it in the subset else simply return b) if(sumTillNow > n) We have a sum which is more than target, and as we don't have negative numbers we cannot form n so we simply return. c) if(i==10) We can have elements till 9 only. So we return 6. Now we pick the i-th element into our subset , increment sumTillNow by i and ask Recursion to do the calculation for i +1 elements. 7. When we return, we backtrack the changes, decrement sumTillNow by i and pop_back() the inserted element. 8. We now ignore the i-th element, so we simply call for i+1 and ask Recursion to do the remaining task. Time Complexity: O(2^N) [ In worst case, we need to include all the elements till 9 to have n] Space Complexity: O(N) [ Height of Recursive Tree]

[@emtiazahmed5333]

I just love your summary & i included this into my note🥰🥰

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@daniyalhussain5231]

This playlist is so so underrated. Fraz you are an absolute legend.

[@aasifali9139]

bhaiya, i dont think you realize how much you are helping me and others by making this gem series. Absolutely Love it. Thx a lot for the effort you are putting in your videos for us. THANKS again..............

[@nithins3895]

I have done this differently And now im seeing your code is more optimized... Thanks for the HW prblms so that we can try and then we can see your way of doing and learning the things clearly Thanks for the video Bhai

[@rounaq_khandelwal]

Loving these series!!

[@maazulhaque7293]

Episode - 14 Done Thanks Fraz bhaiyya

[@alien65629]

solved it by myself with the help of previous combination codes. THANKS FRAZ Bhaiya 😄

[@davv-r5b]

Now In this Type Combination Sum 3 , main change from other types is The Given K value : 1. we have to return vector with k length of elements that sum up to N value: 2. Now main approach for this is to Remember That we have to stop When Our K count expires. 3. And then check whether our sum is N equivalent or Not. 4. Applying Simple Pick And Not-Pick approach . 5. And as we have given that range is 1 to 9 , then there is no element occuring duplicately. 6. And when we will add some element to our Temp Vector , then our Count or K should be change. 7. But not At the time of Not-Picking the element , because the no of elements remains same . /// This is the Summary Of this Lecture /// For more clarity Refer To CombinationSum1 and CombinationSum2 Problems First

[@jayantmishra6897]

rarely i subscribe any channel but whatever content that you are providing makes me to subscribe this channel .

[@DPCODE72]

For the first on Utube who is bringing a quality of good understanding video over the Recursion if he I will keep teaching us like this insane way then it is gonna be 🔥!!

[@mohdumar6990]

Now, I understand combination concept using recursion 👍

[@SahilVanarse-n4x]

Because of him I am able to solve the next questions ...logic building 💪💪

[@nitigyajoshi4658]

sumTillNow can be incremented in function call as well. This was really intuitive. Thanks for the great explaination.

[@ranitbandyopadhyay]

Was not available yesterday. As more and more constraints are introduced, the problems are getting more and more interesting and your explanation also. Good work.

[@jayantmishra6897]

and i have one suggestion for you is that is please display the question for a moment so we get little more idea about that.i know before you start explaining you explain about the question very well but this will be additional point for us.

[@webtechnology6439]

Sir, I am self-building logic without a video watch. Verry Exited 💥💥💥

[@ankushladani496]

Now Understanding Recursion in a good way. Thank you Bhaiya....

[@Abhishek-fo3fc]

Done Understood ❤✅

[@surgeonofdeath8199]

lol i used the trick u used in first question named combination and it worked then checked out ur solution it is same really glad that i was able to do a medium level question myself this time

[@priyanshusingh8971]

Completed lecture and Commeting for better reach

[@aashuvyas786]

very Great Series! i was able to solve this problem wihtout even seeing this video just with help of you previous videos

[@AtomicAkshay]

Notes: The problem requires understanding of both subset and combination problems, once we have that it is somewhat straightforward to solve, important thing was to identify the base conditions for the recursion. Time Complexity: O(n ^ 9) Represents upper bound, although runtime complexity might be lesser due to presence of k Space Complexity: O(n) Excluding size of result array

[@avadhutlohar5181]

#EP_14 Completed Consistency OP 🔥🔥🔥 Congrats for 10K❤ Rise and Shine 🌟

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@ratnasanjay]

Thankyou bhaiya for this session

[@sarojgupta5562]

Fraz bhaiya i am following ur dsa course and its really helpful...thank u for all the content and consistency..thank u bhaiya

[@sanjeevkumar-pk1ko]

If u know completely comb. sum 1, 2 then this problem just take 2 mins : just add some new base conditions void fun(int i,int k,int tar,int sum,vector & subset,vector & ans){ if(i>10){return;} if(tar==sum && subset.size()==k){ ans.push_back(subset); return; } if(subset.size()>k)return; //taking i in ans subset.push_back(i); sum+=i; fun(i+1,k,tar,sum,subset,ans); //backtrack subset.pop_back(); sum-=i; fun(i+1,k,tar,sum,subset,ans); } vector combinationSum3(int k, int n) { vector ans; vector subset; fun(1,k,n,0,subset,ans); if(ans.size()==0){} return ans; }

[@it_08amanagarwal35]

Excellent lecture bro sorry today I am late to comment as I watch the video but intuition behind question is helping me to solve more no of questions❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤

[@mdsufyankhan1029]

L14 done ✅✅ Consistency++ 🔥🔥

[@yashpadiyar4952]

Thankuuuuu ,luvv u bhaiya🤗🤗♥️

[@Lucifer-xt7un]

Congratulations for 10k subscribers 🤩🥳😍

[@anuraggulati2167]

lecture 14 done waiting for the next lecture👌👌 feeling confident now in recursion 😎😎🙌💚💚

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@sadikahmed3045]

Congratulations 👏🎉🎉 for 10k

[@chiragkarnwal6740]

Thanks for the lecture sir💝

[@Gauravkumar-kc6xh]

Great

[@cinemaclockwork215]

It's really helpful

[@jayantmittal6665]

Awesome Content!

[@mohitroshan3856]

Ep 14 done ✌️

[@sagarpokhriyal6926]

Lecture 14 Completed ☑ Congratulations bhaiya for 10k. Many more to come💫 #dsabyfaraz☀

[@divyanshsagar]

Episode 14 done! 🔥🔥

[@singla__sisters2928]

Nice Explanation, Please discuss contest questions as wellll

[@satyammishra6356]

Ep-14 Done ✅

[@ShubhamKumar-lf7ed]

u are great sir

[@anishsingh4750]

Present bhaiya!

[@klvp_techie]

Logic: For every element of an array we have two choices, either to consider it or ignore it if we consider the element update the sum and add it to subset and ask recursion to do the rest and undo all changes you did earlier (# Backtracking) if we ignore it , ask the recursion to do remaining task Base Condition: if sum > target return if length of subset == required check for the sum == target save in ans and return Code: def helper(i,a,k,b,sumTillNow,subset,ans): if sumTillNow > b: return if k == 0: if sumTillNow == b: ans.append(subset[:]) return # if k < 0: # return # if sumTillNow == b: # if k == 0: # ans.append(subset[:]) # return if i > a: return #consider the i sumTillNow += i subset.append(i) helper(i+1,a,k-1,b,sumTillNow,subset,ans) sumTillNow -= i #not considering i subset.pop() helper(i+1,a,k,b,sumTillNow,subset,ans) a = 9 # upper bound of input k = 2 # required length of subset b = 6 # target sum ans = [] subset = [] sumTillNow = 0 helper(1,a,k,b,sumTillNow,subset,ans) print(ans)

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@uavishal777]

Best Explanation 🔥🔥

[@LearnYardYT]

Glad you liked it

[@riyagoel4282]

best content

[@vishalgowrav]

Episode 14 completed! Combination Sum III Here, The problem is the combination of previous two problem but here we want to return the subsets in which the sum shd be equal to n and count of subset cannot exceed k so in order to achieve it We are incrementing sum and Decrementing k (same as previous problems) and in the base condition we have to check for both sum and k using nested if. Time complexity:- O(2 pow n) Space complexity:- O(n)

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@isikamaiti9116]

14 done ✅

[@someshkharat5849]

hii fraz..appreciate everything u r doing for us..just want to ask u if u could please explain the backtracking lil bit more..

[@LearnYardYT]

Yes in coming episodes i will

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@manikgoel9953]

Thanks you bhaiya

[@NikhilTiwari-to7sv]

sir please make a playlist on stacks and queues

[@mohdsaadalikhan7209]

if(k>9-i+1){// required k numbers > remaining numbers return; } this base condition can also be added to further optimise

[@santoshkumarpaul5304]

Bhaiya plz solve leetcode example

[@aveermukherjee6419]

Sir will you provide video explanation for the test problems. I was not able to do two problems. It would be very helpful. And sir you said that you will be starting a basic course consisting of array algos binary search etc. It will be very helpful if you start it early.

[@kamranwarsi12b22]

In the question it is mentioned we cannot use same numbers between 1 to 9 , so can we use that while condition while(i+1==i && i

[@ashokbhardwaj681]

Bhaiya beginner series kab se start hogi pls 🙏 reply

[@anirudrabrahma_0971]

What about exam questions solution discussion...??btw enjoyed another nice video ❤️

[@ecs185_shaileshbharti3]

Reach++: ✌️💥

[@yashbahuguna8135]

done for day 14

[@shalimar_mehra]

Present ! ✔🙌 ok ! It Was Pretty Good but I'm Trying ! I'm facing so many problems ! Can you sir please make an video on [ How to Build logic in program so it was help me for solving my questions ] Thanks a lot sir for this lovely video ! I'm trying my best ! 🙌

[@mohdkhaleeq7468]

Fraz bhai teach Greedy Algorithms topic also

[@ksankethkumar7223]

What is the time complexity of this problem? is it one among these two O(k*9^k) or O(n^2)? Or what is the correct time complexity?

[@DTMASUYASHMISHRA]

Sirr Maine pehle ekk vector of int bana liya usme 1to 9 element daal diye arr usi m pick and ignore it khela ar sum karta gya pehle question jaise arr sari base condition laga dii arr shi hoo gya

[@ammysaini10]

👌❤️

[@vicky-xf5nx]

❤️

[@jayanthipenugonda7274]

why can't we use if(sumTillNow>n || k

[@utpaltripathi9577]

Another base condition for optimization can be- if( ( n - sum ) < ( k * ( k + 1 ) ) /2 ) return; wait! I am explaining also... (n-sum) : It is remaining sum that we have to include. k : number of elements needed to include their value in sum k * ( k + 1 ) ) /2 : sum of first 'k' elements from 1+2+...+k. (minimum possible sum of unique k elements) So think mathematically, if required sum of k unique elements is less than minimum possible sum of k unique elements, then we can't get our result. Correct me pls I am wrong...

[@Lucifer-xt7un]

Consistency ++

[@Anonymous-om5ql]

Bhaiya, where is the HW problem link?

[@utkarshchauhan5827]

Guys I have doubt that Jaise ki bhaiya ne jab sumtillnow==n wali condition lgayi,to unhone sumtillnow>n waali top wali condition comment kardi.inhone jo reason diya wo satisfiied nhi lga ,kyunki yeh condition to important lagi agar k=7 ho and N=11 Ho aur is case me agar yeh condition na ho to hamara control aur aage badhta jayega jaah iski zaroorat bhi nhi hogi aur complexity bharayega,to please koi mera doubt clarify kardo

[@naveen_kotha]

Can I get the Questions which were asked in Recursion Contest 1 as I am unable to attempt it

[@yeswanthh5068]

☺️💚💚🙏🙏🙏

[@pn5563]

Hello I'm mech 17 pass out with 57 pointer in garduation after work 2.6 yr looking for switch in IT industry because in 12th I'm Computer science student then because people suggest us in our town so we select mechanical who go in future to switch so after 1 yr of work in mechanical field i looking class but i don't know how to apply or go I don't have Idea then lockdown happens I'm looking offline class now i join Java course .....also while listening on KZbin DSA is important so I'm here after watching ur video please please guide me how to apply for job after completing course of 6 months please 🙏

[@harshbardhansingh4141]

Bro how to get an internship for a 2nd year student I mean where and how to apply because we don't have any specific experience in the role and the Company how to select us....bcoz sab koi bol dete hai ki ye karlo woh karlo interest pai koi v skill pey sikh kar ke internship kar lo but koi ye nahi batata ki kaise apply kare...itni bheed main hum kaise uss company Mai as a fresher internship paye... Can you make a complete separate video in this topic...🥺🙏

[@emtiazahmed5333]

Bro i wait for 2h 🙃... Aj kitney lare kyu ho giya? Everything is fine??

[@LearnYardYT]

When I rendered the video it didn't come out fine. Then re-rendered, it took time

[@RajputAnkit11]

sad today i am not able to solve and watch this video will do tomorrow sad

[@BurhanAijaz]

Day 14 bhaiya aaj itna late kyu, sab khairiyat

[@ayan84240]

First

[@comic_forever]

aaj no homework problem bhaiya?

[@vivekpaanchal]

New series kab aari hai ?? google join kar ke channel bhul gye 🥲🥲

[@LearnYardYT]

Nahi bro jaldi ayegi Was working on leadcoding.in/ Do check out

[@vivekpaanchal]

@@LearnYardYT kal video aate hi dekh liya tha 😌❤️ , so bhi Jaya karao raat ko bhaiya 🥲🥺

[@dashundev1586]

Uploaded late so watching late

[@akashyadagouda896]

missing Striver here

[@dashundev1586]

And there’s no notification

[@RajputAnkit11]

i worte my own code just forget to stop when i becomes 10

[@akashnigam5321]

Bhai agar tu nhi hoga to pata nhi recursion kaise samajh pate 🥺