L9. Combination Sum II | Leetcode | Recursion | Java | C++
Vložit
- čas přidán 10. 02. 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem Link: leetcode.com/problems/combina...
C++/Java Code: takeuforward.org/data-structu...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
C++ code link: github.com/striver79/SDESheet/blob/main/combinationSum2C%2B%2B
Java code link: github.com/striver79/SDESheet/blob/main/combinationSum2Java
Instagram: instagram.com/striver_79/
tussi great ho :)
def sub_seq(x, sum_sofar, arr, res, i):
if i >= len(x): return
if sum_sofar > 20 : return
if sum_sofar == 20:
res.append(list(arr))
return
arr.append(x[i])
l1 = sub_seq(x, sum_sofar + x[i], arr, res, i )
arr.pop()
l2 = sub_seq(x, sum_sofar, arr, res, i+1 )
return res
Woahhh.... Striver you are doing such an amazing job 🤩🔥
I think in the 9th line an extra check of i-1>0 must alo be applied otherwise will give a runtime error
Amazing concept!! Thank you so much striver bhaiya for this video series !!
nothing wrong in watching the video twice or thrice to get the concepts clear.... Totally worth!!!!
Bro I too watched this 2 times and really helped me
haa mujhe bhi 2nd time me bahut acha samaj aaya
I have watched the complete playlist thrice. And now I am watching it the fourth time. And each time I watch it I get to learn something extra
@@ayushranjan3014 bro don't waste time on watching playlist repetitively, nothing gonna happen.....practice problem as much you can!
@@hi-tk4hu same
Striver is so smart in selecting a perfect example case to explain a concept and the explanation always turns out to be great. Striver, I am extremely grateful for your content.
Iam new to recursion can you tell how recursive call is working inside the for loop?Thanks in advance
@@sudharshan3863 you should make a tree of recursion call to understand how this work (hint :as simple as you know recursion works)
you should watch N queen problem of masterclass of striver L4 there you can get it .
@@sudharshan3863 watch L5, L6 of this recursion series
How can you teach so swiftly, that a noob can also understand it without any doubt. You're amazing Striver, God bless you.
So are you saying we are noob😂
@@akshayrathod7679 wait what?
Beautiful, never watched anyone solving good level recursion problem this much smoothly :)
can you explain why should we take i>ind plz
@@nik3889because we want to pick the first element
Here is an example if the array is 1,1,1,2,2 if I>ind then only we check for repeated thing arr[I] == arr[i-1]
Because we have to take the first element from that consequetive ones and first 2 from that consequetive 2's
So if I> ind then the first element will be picked up and rather duplicates are ignored
ok then please tell why time complexity is 2 power n logn n in brute force
I gave a complete day to combination 1 problem as the code that I came up with while remembering the subsequence sum K problem was a bit different from his code, that is, I was not doing K - arr[ i ] instead just sending K and using sum variable for sum == K and used couple of more base cases, and then making several recursion trees and all that and finally the overall intuition and the internal working is mapped in my mind that I can actually visualize the flow of recursion and touching base cases, it's completely worth it giving full time to each and every problems discussed here as it takes you to whole another level of conceptual understanding
Sir, I never seen such a great level of teaching but I can say ur the one of the best and great tutor.
Thank you sir.
Fun fact : this video is all about to differentiate "ind" and "i"
Hahaa, truee
Most important comment hands down
why not name is something more meaningful! 'i' is a unspoken iterator in programming world, but it gets confusing here!
you are the greatest teacher in the field of DSA trust me.
* This solution is same as "Print all the subsets of the given array, but without duplicates".
* Why means, here the combination and there the subset sounds similar.
* We can say like "Print all the subsets with sum 'target' of the given array without duplicate subsets".
For printing all the unique subset, we would have got each unique subset at each recursion node and print them all.
But here though, it is enough to print the subset with a particular sum.
In this way, the Subset II and Combination Sum II looks pretty much similar :)
Beautifully explained, recommend others watch at least two times to get a good grip on this pattern and problem.
thank you bhaiyya your i have been trying to study these things for the last couple of years but do not able to but the way you explain it wow! . really greatfull. may god serve all the best things to you.😊
Question is solves in very high level way 1st time watch video I didnt understand the concept after watching 2-3 times I understand full concept due to this type ans we can grow our skills best code and explanation on hole yt all just using "take" and "non take" you are also using same concept but in different manner so time complexity decrease thanks for great explanation 😀😀❤️
Note that we choose elements only from the right in order to avoid choosing duplicate candidates.
Its a great solution and excellent explanation. My solution went from beating 5% to 98%. And also great choice of test case for explanation.
TC: 23:52
code(cpp): 28:05
recursive tree : 18:07
Good explanation. I've come up with, imo, a slightly more intuitive solution based more closely on the pick/non-pick Combination Sum 1 solution:
void allCombToSum(vector candidates, vector& ans, vector& comb, int idx, int target)
{
// BASE CASE 1
if (target == 0)
{
ans.push_back(comb);
return;
}
// BASE CASE 2
if (idx == candidates.size() || candidates[idx] > target) return;
// ELSE pick ...
comb.push_back(candidates[idx]);
allCombToSum(candidates, ans, comb, idx+1, target - candidates[idx]);
comb.pop_back();
// ... and non-pick by recursing on the next available candidate
// which is not the same as the current candidate.
idx++;
while (idx < candidates.size())
{
if(candidates[idx] != candidates[idx-1])
{
allCombToSum(candidates, ans, comb, idx, target);
break;
}
idx++;
}
}
vector combinationSum2(vector& candidates, int target)
{
sort(candidates.begin(), candidates.end());
vector ans;
vector comb;
allCombToSum(candidates, ans, comb, 0, target);
return ans;
}
abhi bhi same error de raha h 2nd base case mei
if(index == candidates.size() || candidates[index] > target)
This explanation is awesome. Kudos to your efforts.
Thank you for putting up this video with thorough explanation. Some questions. Suppose k_2 is the number of elements to be inserted into the HashSet, that is, the number of combinations that satisfy the target sum. Then, since insertion into HashSet is constant time, do we not have this log(k_2) factor? Shouldn't it just be 2^t * (k_2) as a result? And if we were using ordered set then we would have 2^t * (k_2 log(k_2))?
I am also not completely sure about explanation for the 2^t * k time complexity mentioned in the previous lesson, where t is the target sum and k is the average number of elements in one combination (it was ambiguous in the previous video because you said average length of the data structure and there are two data structures, the vector and the vector). It seems like from the explanation in the past video that we are saying that 2^t is the maximum possible number of choices (take/not take) that it takes to get one combination and then it takes k time to put the elements into the data structure.
I am thinking what is meant is that it takes you 2^t recursive calls at maximum to find one valid combination, adding to the vector would be included in this cost as part of the operations that happen during the method. Then, if we let k be the average number of combinations, that is, the average number of elements in the vector we return, we have 2^t * k.
Will be glad for any clarification
no actually answer should be in lexicographical you must sort it after putting into a vector so it will actually be 2^t log k + klogk + k
Hello Dada...Thank you for this wonderful video..😇😇 I live near your location where you lived with your parents.😄😄
One thing that I want to say, I can understand logics and algorithms that you make us understand . But how to remember all logics and algorithms for long time.
Understanding is easy but how not to forget it ?
Give some tips. And also continue your poland blogs. Best wishes
I hope one day to see you and thank you so much for all your effort to help us to understand very tough topics all respect to you bother
when at index IDX either pick that element and go to the index(IDX+1) or don't pick that element and go to the index (next_greater[IDX])the first case when we are picking an element then we took an element x as our yth element and we don't want another the element x to be picked as the yth element once again that's why when we aren't picking any element at the index IDX then rather than moving to index IDX+1 we are moving to index next_greater[IDX].
Basically, the main motive is to not pick the same element at the same index again and again.
Let me complete it for him 22:28 : Toh fourth kya ghanta pick krenge... '😂
Thanks for for the amazing video bhaiya...
😂😂
I have been following Striver for the last one year. I just watched the video till 15:31 and was able to code it on my own.........Thanks a ton Striver Bhaiya...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
that was brilliant explanation for this qsn...hats off to u bro
The condition at 29:35 was explained so well....💯💯💯
thank you so much for explaining each and every step of the recursion tree..love your videos
superb!! how smoothly he explained
No one can Explain Better than you , Brilliant Outstanding Explanation , There is No Regret in my Life except knowing about you late in my 3rd year of B.E.
same regret🥲
I understood the solution at around 17 min, but I watched the full video to support you
Hi striver! Thank you so much for your videos!!! Its very helpful!
One small doubt.
Could you please tell what is the auxiliary space taken by stack?
Is it N, if N is the length of given array?
It's the number of function calls waiting in the stack space, if number of function calls are n then its n otherwise we have to find how many... and sometime we don't know the count of it since we aren't sure about how many calls will be required to get it to the final answer...
For java solution at line 9, for the first 0 the statement a[I] = a[i-1] would throw out of bound exception because 0-1 = -1 is a invalid index. I think instead of using AND logic there we can put the second condition inside the first if statement.
Phli condition hi false hojaegi i>ind vali to vo 2nd condition chk hi nhi krega isliye chl jaega
After Watching till 10 minutes, I was able to solve myself. Thanks
Can try this logic too, in this logic we are using while loop and incrementing index to ensure unique subset.
class Solution {
public void helper(int[] nums, int n, int idx, List temp, List ans){
if(idx == n){
ans.add(new ArrayList(temp)); // Add a new ArrayList containing the elements of temp
return;
}
// Include the current element
temp.add(nums[idx]);
helper(nums, n, idx + 1, temp, ans);
temp.remove(temp.size() - 1); // Backtrack
// Skip duplicates and exclude the current element
while (idx + 1 < n && nums[idx] == nums[idx + 1]) {
idx++;
}
helper(nums, n, idx + 1, temp, ans);
}
public List subsetsWithDup(int[] nums) {
List ans = new ArrayList();
List temp = new ArrayList();
Arrays.sort(nums); // Sort the array to handle duplicates
helper(nums, nums.length, 0, temp, ans);
return ans;
}
}
Literally addicted to your teaching....🍻🍻
Recursion was always a nightmare, with the pattern in hand, it has become easier to analyse and get an intuition about the problem. Thank you.
i am just super grateful that i found you early in my college days.
I've been following your A-Z Sheet for a while now. It's better than paid course. Thank you very much!!!
Please continue this Bhaiya! very helpful
Striver, you are legend.
I would have taken me a day to get to know if there was no video like this to understand.
Thanks, Striver to make this simple to understand😇
bhai ye space complexity k*x kyu hua...humne toh bas ek ds vector use kra hai aur jo hum vec bna rhe hein woh toh count he nhi hota na complexity ki taraf...so isn't it should be O(k)...since average lenght of every combintion is k
Why looping from index to n-1 is not considered for time complexity? please explain
Excellent Explanation
Makes easy to solve questions with duplicates
The most clear explanation
Hey can we say that whenever we need to add something and then remove it then we are always applying backtracking in it? (Like adding, doing recursion and then restoring).
yes
Plzz explain the concept behind I>idx
Striver, this line of code in java:
if(i>ind && arr[i]==arr[i-1]) continue;
Does the 'continue' mean skip the i th value by telling the for loop to ignore the next lines and start over by incrementing i ? I don't really get what "continue" does.
Is my answer to: "Why i>ind check added?" correct?
We are checking for the next element we are going to choose in the for loop and we are currently standing at ind in the candidates array. If i==ind, this the first loop in the for loop and arr[ind] can be chosen if it's the first time. Otherwise(IF i> ind), it means this is NOT the first time the for loop is running and we should check if arr[i] == arr[i-1], because if it is we can't choose it anymore, because we are sure that we chose the first one(when i==ind).
AND THANK YOU FOR THE AMAZING CONTENT!!!!!!!!!!
thank you so much your explanation is in another level bro
10:40 to 11:45 concept clear ho gya .... thanks
17:32 .Can anyone explain to me if we have removed the ith element then why don't we need to add it again to the target.. for example, if f(2,2,[1,1]) calls f(3,1,[1,1,1]) so if we remove the 1 from array of the f(3,1,[1,1,1]) how will target still be 2 in f(2,2,[1,1]).
draw the recursion tree you will understand it better. and watch previous videos where striver explained left recursion and right recursion. in this video he did target - arr[i] as a parameter. so originally the target didn't change it remains f(2,2,[1,1]). but target did change for the picked element because its another recursion inside f(2,2,[1,1]) where he passed target - arr[i] as parameter. so basically the changes happened only for f(3,1,[1,1,1]) "1 subtracted" and f(4,0,[1,1,2]) "2 subtracted". here its still working as pick not picked but differently where it has more option to pick or not pick
Excellent explanation!
Very nicely explained thank you
It was getting so hard to understand why to use the for loop and how will that work but you made it very clear. Thank You so much Striver!
This seems like a perfect DP problem where there is lot many recursion repetition.
please any one explain the logic of i > find i am confused for which case this will be used
UNDERSTOOD.........Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
in time complexity we are using a loop from Ind to N in every recursion call ..how it is not N^2 (N square) but 2^N?? someone plz explain..
Understood, just a small doubt...
In these types of questions, there should be no zero in the array na??
because in the case of combi. sum I, it will form an infinite loop and in the combi. sum II, base case will make us miss some of the possible cases...
If anyone's confused why we use sorting:
Read the 2nd and 3rd line of the question. You might have tackled those problems by using set data structure.
But that increases the space complexity.
In order to use less space (and obviously more time) striver used sorting to tackle both problems with one approach.
can you please explain why the time for converting adding list to a set is K logK?
@@vinayakgandhi5690 Insertion in set data structure takes log n time if you have n elements.
If you have k insertions to do, it becomes k log k
@@parthsalat Thank you so much for your reply Sir, but isn't the time of insertion depends upon the implementation, in c++ it is O(logn) but in java it is O(1), so the hashSet solution should work in java, right?
@@vinayakgandhi5690 Yes, if you are using Hashset then insertion will be O(1).
So inserting N elements in set would take O(N) time.
@@parthsalat But I don't think that we can insert a vector into a hashset...how will c++compiler hash its value....
In recursive solutions, time complexity was 2^n only when each recursion call has two options (i.e. either pick or not pick).
But, in this question, for every recursive call, we have 'n' options to pick. We are calling function for each index one by one and for that index we are again calling next indices one by one.
So the worst case time complexity should be n^n.......right ? (the case where all elements given in the array are unique)
Plz someone explain this
No at the time we discuss time complexity we assuming we have n district no so that possible combination is 2^n *k where k is avg length of vector
If logS factor in time comp of brute force is for insertion of s elements in set then why we have taken k in time complexity
In this one is it necessary to be more selective with that you pick when you could just use a hashset to filter out the duplicates? Is the motivation here to simply do fewer unnecessary recursions?
cant we can say its just extension of combination sum 1
steps -
1. store count of every element in hashtable
2. follow same approach as combination sum 1, just pass additional parameter as count
3. and add if() check for count, if(count < map[candidates[index]])
Time and space complexity discussion: 23:48
Hi , at 5:13 , didnt really understand this part , how can a change from list to set ,introduce an extra log(n) in the complexity , can someone explain
because elements in a set are kept in sorted order, hence it has an overhead.
Why in brute force we are doing ind+1 in take? We can do same way like combination and put in set.
great video. Thank you for this❤
This question is different from subsequences sum because in that
For candidates {1,1,2} and target 3
The subsequences will be {1,2} and {1,2}
However the combination II will be just {1, 2}
Feel the recursion
But what if the target is not achieved and the recursive step for index = n is reached. as we didnt mention it in the basecase(idx==n) how its gonna return??
same doubt
If you want the slightiest change in Combination Sum I to convert the code to Combination Sum II, just add a while condition as follows:
class Solution {
public:
vector combinationSum2(vector& candidates, int target) {
vector ds;
vector ans;
sort(candidates.begin(), candidates.end());
func(0, target, candidates, ds, ans);
return ans;
}
void func(int ind, int target, vector& candidates, vector& ds, vector& ans) {
if(target==0)
{
ans.push_back(ds);
return;
}
if(ind==candidates.size())
{
return;
}
if(candidates[ind]
Would this give a TLE?
@@shashamnk2525 ofc no
not able to understand i > index condition as 4rth call we be neglected as in fig at 31:16 by the reason v[i]==v[i-1] why addinng one more condition of i>ind
Kadak explanation
inside for loop ...should we not write the if condition like this ?? if(i>ind || arr[i]==arr[i-1])
to skip dupes
commenting before watching the video coz we know video will be awesome
Amazing explaination.
Just a naive question: In the earlier question striver used simple recursion to loop through the elements of the array but in this one he used for loop to loop through every element. Can't we use the same template here!
Someone please explain!
we can, but it takes more time to remove the duplicate elements. Here in the given array, we can have similar elements that form duplicate answers to avoid those we are using for loop in which we are trying to escape the similar elements. whereas in previous question all the elements are distict
Getting in love with recursion more than my crush....
U need that love otherwise it's impossible to be consistent in these topic..
C++ code starts at 28:05
Awesome explanation
I'm confused in just one thing. When findCombination(3,1,arr,ans,ds) will be called and the if (arr[i]>target) will become true it's supposed to break. Where will the execution go from there? What I understand is that break statement will cause it to exit the for loop but how's that supposed to work since there's no code outside the for loop. How will this be handled? So will the break cause it to just return from the current call? Somebody please explain.
yes after break it return from the current recur call and then pop statement of last call will be executed
@@saketmehta6697 thank u buddy
I am not able to understand why are we using the condition i>ind.can anyone help me?
I didn't get the explanation at start of video , converting ans list to set would fix the duplicate issue. Question says given array element cannot be reused for combination. So how can deduplicating external list would fix it when internal list contains same element multiple times
he is the best source for understanding DSA on youtube just like pepcoding and adhitya verma!
For getting one single sequence, we can prevent the duplicacy by 9th line condition, but how we are preventing the same sequence to be added in our answer for the next iteration. i.e how we are skipping the 1st index to be picked, after we picked the 0th index. STILL CONFUSED.
I think in the 9th line an extra check of i-1>0 must alo be applied otherwise will give a runtime error
it has already been applied in the form of i > ind
can someone tell me that, wont array.sort takes n log n TC, apart from 2^t * K
why cant we do ind+1 instead of i+1?
is it because the duplicates will be allowed if we use ind+1 .can someone clear my doubt?
22:30 That hindi accent was awesome bhaiya
loved your hindi accent
Good explanation!!!!..... But why am i getting duplicates in output using this c++ code?
you might called the findcombination function again in the for loop after pop operation.. I too did this but afterwards got the point that we are in loop so it's loop's responsibility to do it again and again
Sir I have question that if (arr[i]>target)
{
Break;}
So how's it going to its previous calling function function cause their is return statement at all just a break
I am getting duplicates, so storing them in a set will make a extra time complexity right
how can I overcome that
Code has been explained
can someone explain how the time complexity is 2^n and not n^n for n unique elements
At every stage we are having two choices for n elements
Hey,can we use unique stl function on ans vector at the end and just return it?
yes
Plzz anyone reply....... Humne jab return kiya to us container m se pop kiya... Par target value ko bhi pehle jitna krna pdega jaisa previous lectures m kiya?
void backtrack1(vector &candidates, vector &result, vector ¤t, int start, int target)
{
if (target == 0)
{
result.push_back(current);
return;
}
if (start >= candidates.size() || target < 0)
{
return;
}
// include
current.push_back(candidates[start]);
backtrack1(candidates, result, current, start + 1, target - candidates[start]);
current.pop_back();
// exclude
int next = start + 1;
// skip duplicates
while (next < candidates.size() && candidates[start] == candidates[next])
{
next++;
}
backtrack1(candidates, result, current, next, target);
}
vector combinationSum1(vector &candidates, int target)
{
vector result;
vector current;
sort(candidates.begin(), candidates.end()); // sort to handle duplicates
backtrack1(candidates, result, current, 0, target);
return result;
}
target = 7 nums = [2,3,6,7]
i mean jab recursive call solve hojayega na
like func(2)
-- func(1) assume ye solve hogaya
fir idhar 2 hi hoga na
same doubt
Thank you !!!! Wonderful :)))
Reduce the target by arr[i],call the recursive call for f(idx + 1,target - 1,ds,ans) after the call make sure to pop the element from the ds.(By seeing the example recursive You will understand).
can anyone why after popping out the values from the ds the candidates value is not added to the target actually it should right otherwise the target remains same right? even afer popping out but without additon of the values the code runs well
we should add index==n condition also ,cuz there might be case when we have not met target yet but we crossed the array bound
have you got the answer of this question?
I'm still wondering about it...
I think, we are breaking the execution when arr[I]> target so is this the answer that we will not great there or else?
sir one question for you. in for loop as our first element is 10 so it will not add becouse it is greater than target . so our i will be increase but problem is our i is initialize with idx, by our idx is 0 so how our i will go to next index to check only this is my weak point where i am stuck to make its dry run. other all the concept i understand if you can please make one video on its will be very benifitial for me and i think for other also
No, look at the parameters. The index is i+1, which means when the for loop runs again index is not still 0. No it's i + 1 which is 1. So the for loop runs from 1 to the end. Get it? I hope I made it clear.