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.
@@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 .
For anyone who is confused between i and idx, Let me explain idx is that index which tells what value to keep in the data structure and i is just traversal of array example : 14:27 When function is f(2,2,ds(1,1)) it calls for f(3,1,ds(1,1,1)) (here i==idx) then it returns since value is exceeding the target . after it calls for f(4,0,ds(1,1,2) here i>idx but arr[i]!=arr[i-1] meaning ,this is the first time we are encountering the element (unique element) . After this call function does'nt goes to f(4,0,1,1,2)(i>idx) cause arr[i]==arr[i-1] (duplicate element) so function returns here itself.
after it calls for f(4,0,ds(1,1,2) here i>idx but arr[i]!=arr[i-1] meaning ,this is the first time we are encountering the element (unique element) . can you please tell me the value of i and idx when it exceeds i am unable to understand
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
@@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
* 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 :)
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...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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]
if (arr[i] > target) return; This line effectively stops the function from continuing any further in this iteration of the loop, as all subsequent elements will also be too large due to the sorted nature of the array.
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
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; }
@@nikhil5965 use this to avoid out of bound in recursion calls: the first condition make sures you are in the bounds of array if(index target){ return; }
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.
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.
@@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?
so basically the optimal solution that striver explained is a backtracking approach where we pruned(cut off) the unnecessary paths early!! by exploring all the possibilities at each step
we did not require the base case of idx>arr.length becasue whenever we would reach that case, it wouldn't enter the loop and the function would return.
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 😀😀❤️
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
code in java using hashsets : package striver_recursion; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class combinationsum_2 { public static void main(String[] args) { int a[] = {1,1,1,2,2}; Set< List>s= new HashSet(); int sum = 4; ArrayList l = new ArrayList(); // int k=2; f(0, a, l, 4,s); System.out.println(s); } public static void f(int i, int a[], ArrayList l, int sum,Sets) { if (i == a.length) { if (sum == 0) { s.add(new ArrayList(l)); } return; } if (sum >= a[i]) { l.add(a[i]); f(i+1, a, l, sum - a[i],s); l.remove(l.size() - 1); } f(i + 1, a, l, sum,s); } }
Well Understood the Combination Sum I, Combination Sum II with the help of massive explanation ! Now I solved Combination Sum III on my own and that too within 10 mins. As usual Striver things !!
If you're are wondering why didn't he solve this problem using the similar concept that he used in Combination Sum 1 then read this: You can actually do it using the same technique as of that problem, which would be the correct solution and since you already are familiar with that technique, it makes sense for you to use that technique only. But the thing is that Leetcode is not accepting the solution, and would throw you a TLE. So you have to use this new technique which is much better and optimised. However, if you want to see the solution of this problem with the Combination Sum 1 Technique then here you go: class Solution { public List combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); Set result = new HashSet(); result = findSum(0,candidates,target,result,new ArrayList()); List ans = new ArrayList(result); return ans; } public Set findSum(int index, int[] candidates, int target, Set result, List list){ if(index>=candidates.length){ if(target==0) result.add(list); return result; } list.add(candidates[index]); findSum(index+1,candidates,target-candidates[index],result,new ArrayList(list)); list.remove(list.size()-1); findSum(index+1,candidates,target,result,new ArrayList(list)); return result; } }
//below solution is accepted with combination sum 1 technique. class Solution { public List combinationSum2(int[] candidates, int target) { List result = new ArrayList(); Arrays.sort(candidates); findCombinations(0, candidates, target, result, new ArrayList()); return result; } private void findCombinations(int index, int[] candidates, int target, List result, List ds) { if(index == candidates.length) { if(target == 0) result.add(new ArrayList(ds)); return; } if(candidates[index]
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.😊
i will be completely honest here , i watched L6,L7,L8 and after watching those i myself solved this question which was in L9. And executed it in java. i used hashset and arraylist as object class in it. im actually improving and im realy proud.
you barely changed anything dude, if you actually cracked this for loop logic in this video then you are a genius. Just using hashset, that everyone can do.
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.
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; } }
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: ans = [] arr=[] def funcall(index,sumtillnow,arr): if(sumtillnow==target): ans.append(arr.copy()) return if(sumtillnow>target): return for j in range(index,len(candidates)): arr.append(candidates[j]) funcall(j,sumtillnow+candidates[j],arr) arr.pop() for i in range(len(candidates)): arr.append(candidates[i]) funcall(i,candidates[i],[candidates[i]]) arr.pop() return ans
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
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
Python code class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: ans =[] candidates.sort() ds=[] self.findcombinations(candidates,target,0,[],ans) return ans def findcombinations(self,arr,target,ind,ds,ans): if target==0: ans.append(ds.copy()) return for i in range(ind,len(arr)): if i>ind and arr[i]==arr[i-1]: continue if arr[i]>target: break ds.append(arr[i]) #not working ? because we are passing by reference and at the end ds array becomes [] null so we get null in the ans self.findcombinations(arr,target-arr[i],i+1,ds,ans) ds.pop()
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}
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?
On naked eye, tough to see, you can compare with my solution given in the description. You will find something for sure.. also it is giving tle on submit or on local ide?
@@takeUforward its showing tle in leetcode's compiler and i checked the code but can't find the difference.. thanks for replying i am still trying to find out
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...
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!!!!!!!!!!
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.
I was late to get to this channel but i have to admit that it's the best on youtube on anything to do with algorithms. If you don't understand algorithms from this channel, then algorithms as a concept is not your thing
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?
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
Please help me understand the time complexity TC : 2^n * K K is for insertion of ds vector in ans vector? does adding a vector in 2d vector costs O(n) ?
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).
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]])
checking the code at 28:00 and at 5:14, you said we will be going to use Set, but we didnt use, and still it is working , still it is the same time complexity right? i used take /not take i got TLE , but i used this , it passed all test cases, i am not able to understand, how it has decreased the time complexity here exactly?
I had the same thought process too. We are sorting the initial array. So we still seem to have log in the time complexity even with this solution isn't ?
I'm a bit confused about the space complexity --- why do we still only say that it's k * x where x is unknown here? Since we can use each element at most once in a valid subsequence (as opposed to the last video where the elements are infinite supply), can't we say that x would be bounded by 2^n, since that's the total number possible subsequences? Would appreciate if anyone can 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...
Greate Explanation, just came up with same logic in Combination-II * Similar to Combination-I just avoiding duplicates * Fastrer than 100% of C++ solutions void helper(int i, vector& arr, int t, vector&ans, vector& sub) { if (t == 0) { ans.push_back(sub); return; } if (i == arr.size() || t - arr[i] < 0) return; // check for validity , if we can pick sub.push_back(arr[i]); helper(i + 1, arr, t - arr[i], ans, sub); // to pick sub.pop_back(); // remove while coming back and pick next nonPicked while ((i < arr.size() - 1) && (arr[i + 1] == arr[i])) i++; // avoid duplicates helper(i + 1, arr, t, ans, sub); // for not pick } vector combinationSum2(vector& candidates, int target) { sort(candidates.begin(), candidates.end()); vectorans; vectorsub; helper(0, candidates, target, ans, sub); return ans; }
why we are not following pick and not pick here and have multiple options to pick from . In previous problems we either pick or not pick an element and then move forward
transform the initial array to only contain unique elements, and modify the code of combination sum I to always increment index, that'd also solve this problem
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.
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
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
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?
For anyone who is confused between i and idx, Let me explain
idx is that index which tells what value to keep in the data structure and i is just traversal of array
example : 14:27 When function is f(2,2,ds(1,1)) it calls for f(3,1,ds(1,1,1)) (here i==idx) then it returns since value is exceeding the target . after it calls for f(4,0,ds(1,1,2) here i>idx but arr[i]!=arr[i-1] meaning ,this is the first time we are encountering the element (unique element) . After this call function does'nt goes to f(4,0,1,1,2)(i>idx) cause arr[i]==arr[i-1] (duplicate element) so function returns here itself.
after it calls for f(4,0,ds(1,1,2) here i>idx but arr[i]!=arr[i-1] meaning ,this is the first time we are encountering the element (unique element) . can you please tell me the value of i and idx when it exceeds i am unable to understand
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
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
@@AnirudhRSharma set has logn time complexity for insertion
TC: 23:52
code(cpp): 28:05
recursive tree : 18:07
* 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 :)
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.
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...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Let me complete it for him 22:28 : Toh fourth kya ghanta pick krenge... '😂
Thanks for for the amazing video bhaiya...
😂😂
you are the greatest teacher in the field of DSA trust me.
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!
I still don't understand the i>ind part
can anyone please elaborate me?
It demands your complete attention, grateful to have a mentor like you striver sir.
Note that we choose elements only from the right in order to avoid choosing duplicate candidates.
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
#include
using namespace std;
void findCombination(int ind, int target, vector &arr, vector &ans, vector &ds) {
if (target == 0) {
ans.push_back(ds);
return;
}
if (ind >= arr.size()) return;
if (target >= arr[ind]) {
ds.push_back(arr[ind]);
findCombination(ind + 1, target - arr[ind], arr, ans, ds);
ds.pop_back();
}
int j = ind + 1;
while (j < arr.size() && arr[j] == arr[ind]) j++;
findCombination(j, target, arr, ans, ds);
}
vector combinationSum2(vector &candidates, int target) {
sort(candidates.begin(), candidates.end());
vector ans;
vector ds;
findCombination(0, target, candidates, ans, ds);
return ans;
}
My code
if (arr[i] > target) return; This line effectively stops the function from continuing any further in this iteration of the loop, as all subsequent elements will also be too large due to the sorted nature of the array.
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
Putting that list in ans will take constant time as it's just ans.add().Didn't know how they came up with K.
Time and space complexity discussion: 23:48
Beautifully explained, recommend others watch at least two times to get a good grip on this pattern and problem.
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)
@@nikhil5965 use this to avoid out of bound in recursion calls:
the first condition make sures you are in the bounds of array
if(index target){
return;
}
UNDERSTOOD.........Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
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....
so basically the optimal solution that striver explained is a backtracking approach where we pruned(cut off) the unnecessary paths early!! by exploring all the possibilities at each step
we did not require the base case of idx>arr.length becasue whenever we would reach that case, it wouldn't enter the loop and the function would return.
Hint : This question is basically find the unique subsets with no repetition whose sum equal to target. Same approach as subset sum 2.
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 😀😀❤️
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
Literally addicted to your teaching....🍻🍻
The condition at 29:35 was explained so well....💯💯💯
code in java using hashsets :
package striver_recursion;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class combinationsum_2 {
public static void main(String[] args) {
int a[] = {1,1,1,2,2};
Set< List>s= new HashSet();
int sum = 4;
ArrayList l = new ArrayList();
// int k=2;
f(0, a, l, 4,s);
System.out.println(s);
}
public static void f(int i, int a[], ArrayList l, int sum,Sets) {
if (i == a.length) {
if (sum == 0) {
s.add(new ArrayList(l));
}
return;
}
if (sum >= a[i]) {
l.add(a[i]);
f(i+1, a, l, sum - a[i],s);
l.remove(l.size() - 1);
}
f(i + 1, a, l, sum,s);
}
}
C++ code starts at 28:05
Well Understood the Combination Sum I, Combination Sum II with the help of massive explanation ! Now I solved Combination Sum III on my own and that too within 10 mins. As usual Striver things !!
Its a great solution and excellent explanation. My solution went from beating 5% to 98%. And also great choice of test case for explanation.
If you're are wondering why didn't he solve this problem using the similar concept that he used in Combination Sum 1 then read this:
You can actually do it using the same technique as of that problem, which would be the correct solution and since you already are familiar with that technique, it makes sense for you to use that technique only. But the thing is that Leetcode is not accepting the solution, and would throw you a TLE. So you have to use this new technique which is much better and optimised.
However, if you want to see the solution of this problem with the Combination Sum 1 Technique then here you go:
class Solution {
public List combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
Set result = new HashSet();
result = findSum(0,candidates,target,result,new ArrayList());
List ans = new ArrayList(result);
return ans;
}
public Set findSum(int index, int[] candidates, int target, Set result, List list){
if(index>=candidates.length){
if(target==0) result.add(list);
return result;
}
list.add(candidates[index]);
findSum(index+1,candidates,target-candidates[index],result,new ArrayList(list));
list.remove(list.size()-1);
findSum(index+1,candidates,target,result,new ArrayList(list));
return result;
}
}
//below solution is accepted with combination sum 1 technique.
class Solution {
public List combinationSum2(int[] candidates, int target) {
List result = new ArrayList();
Arrays.sort(candidates);
findCombinations(0, candidates, target, result, new ArrayList());
return result;
}
private void findCombinations(int index, int[] candidates, int target, List result, List ds)
{
if(index == candidates.length)
{
if(target == 0) result.add(new ArrayList(ds));
return;
}
if(candidates[index]
This explanation is awesome. Kudos to your efforts.
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.😊
i will be completely honest here ,
i watched L6,L7,L8 and after watching those i myself solved this question which was in L9.
And executed it in java.
i used hashset and arraylist as object class in it.
im actually improving and im realy proud.
you barely changed anything dude, if you actually cracked this for loop logic in this video then you are a genius. Just using hashset, that everyone can do.
Ye kaafi mushkil sawal tha. Sukriya acche se samjhane keliye ❤
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🥲
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.
22:30 That hindi accent was awesome bhaiya
loved your hindi accent
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;
}
}
I've been following your A-Z Sheet for a while now. It's better than paid course. Thank you very much!!!
I couldn't understand that part -->if(i>ind .....)
Excellent Explanation
Makes easy to solve questions with duplicates
10:40 to 11:45 concept clear ho gya .... thanks
class Solution {
void f(int ind,int[] arr,int target,List ans, List ds){
if(target==0){
ans.add(new ArrayList(ds));
return ;
}
for(int i=ind;iind && arr[i]==arr[i-1]) continue; // skip if case of duplicate element in array
if(arr[i]>target) break; // break when element is greater than target
ds.add(arr[i]);
f(i+1,arr,target-arr[i],ans,ds);
ds.remove(ds.size()-1);
}
}
public List combinationSum2(int[] arr, int target) {
List ans=new ArrayList();
Arrays.sort(arr);
f(0,arr,target,ans,new ArrayList());
return ans;
}
}
Pick/Not pick Take/Not take approach:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort(reverse=True)
output = []
stack = []
def backtrack(i, total=0):
if total == target:
output.append(stack.copy())
return
if i >= len(candidates) or total > target:
return
stack.append(candidates[i])
backtrack(i+1, total+candidates[i])
stack.pop()
while i+1 < len(candidates) and candidates[i] == candidates[i+1]:
i += 1
backtrack(i+1, total)
backtrack(0)
return output
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
arr=[]
def funcall(index,sumtillnow,arr):
if(sumtillnow==target):
ans.append(arr.copy())
return
if(sumtillnow>target):
return
for j in range(index,len(candidates)):
arr.append(candidates[j])
funcall(j,sumtillnow+candidates[j],arr)
arr.pop()
for i in range(len(candidates)):
arr.append(candidates[i])
funcall(i,candidates[i],[candidates[i]])
arr.pop()
return ans
Striver, you are legend.
I would have taken me a day to get to know if there was no video like this 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
Striver can make any problem.super easy 📈📈📈
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
Python code class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans =[]
candidates.sort()
ds=[]
self.findcombinations(candidates,target,0,[],ans)
return ans
def findcombinations(self,arr,target,ind,ds,ans):
if target==0:
ans.append(ds.copy())
return
for i in range(ind,len(arr)):
if i>ind and arr[i]==arr[i-1]:
continue
if arr[i]>target:
break
ds.append(arr[i]) #not working ? because we are passing by reference and at the end ds array becomes [] null so we get null in the ans
self.findcombinations(arr,target-arr[i],i+1,ds,ans)
ds.pop()
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}
Plzz explain the concept behind I>idx
I understood the solution at around 17 min, but I watched the full video to support 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!
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
class Solution {
public:
void helper(vector &ans,int idx,int n,int sum,vector &arr,vector &v){
if(sum == 0){
ans.push_back(v);
return;
}
for(int i=idx;i
On naked eye, tough to see, you can compare with my solution given in the description. You will find something for sure.. also it is giving tle on submit or on local ide?
@@takeUforward its showing tle in leetcode's compiler and i checked the code but can't find the difference.. thanks for replying i am still trying to find out
Try to find, if you don’t get I will check this at night after my office hours..
@@takeUforward thanks for help
@@harshith6245
In helper function,
for(int i=idx;i
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...
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!!!!!!!!!!
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
thank you so much for explaining each and every step of the recursion tree..love your videos
Please continue this Bhaiya! very helpful
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
I was late to get to this channel but i have to admit that it's the best on youtube on anything to do with algorithms. If you don't understand algorithms from this channel, then algorithms as a concept is not your thing
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?
Getting in love with recursion more than my crush....
U need that love otherwise it's impossible to be consistent in these topic..
that was brilliant explanation for this qsn...hats off to u bro
What if we store elements in a set and then perform subsequence sum = k ??
i am just super grateful that i found you early in my college days.
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
he is the best source for understanding DSA on youtube just like pepcoding and adhitya verma!
Please help me understand the time complexity
TC : 2^n * K
K is for insertion of ds vector in ans vector?
does adding a vector in 2d vector costs O(n) ?
we assume k be the length of vector we are inserted in 2d vector
so, it will take k time to be inserted
@@Love-xs9mk ok so you mean,
Vector insertion in 2d vector can take time of o(n)
@@foziezzz1250 yes , as we are inserting a vector not a single element
@@Love-xs9mk got it, thanks 👍🦁
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
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]])
checking the code at 28:00 and at 5:14, you said we will be going to use Set, but we didnt use, and still it is working , still it is the same time complexity right?
i used take /not take i got TLE , but i used this , it passed all test cases, i am not able to understand, how it has decreased the time complexity here exactly?
I had the same thought process too. We are sorting the initial array. So we still seem to have log in the time complexity even with this solution isn't ?
Very well explained 🙂🙂striver
The most clear explanation
I'm a bit confused about the space complexity --- why do we still only say that it's k * x where x is unknown here? Since we can use each element at most once in a valid subsequence (as opposed to the last video where the elements are infinite supply), can't we say that x would be bounded by 2^n, since that's the total number possible subsequences? Would appreciate if anyone can explain!!
Can someone explain at 9:30 i m confused he was suppose to pick the 3 index but he is picking up 4th index
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...
Greate Explanation, just came up with same logic in Combination-II
* Similar to Combination-I just avoiding duplicates
* Fastrer than 100% of C++ solutions
void helper(int i, vector& arr, int t, vector&ans, vector& sub) {
if (t == 0) {
ans.push_back(sub);
return;
}
if (i == arr.size() || t - arr[i] < 0) return; // check for validity , if we can pick
sub.push_back(arr[i]);
helper(i + 1, arr, t - arr[i], ans, sub); // to pick
sub.pop_back(); // remove while coming back and pick next nonPicked
while ((i < arr.size() - 1) && (arr[i + 1] == arr[i])) i++; // avoid duplicates
helper(i + 1, arr, t, ans, sub); // for not pick
}
vector combinationSum2(vector& candidates, int target) {
sort(candidates.begin(), candidates.end());
vectorans;
vectorsub;
helper(0, candidates, target, ans, sub);
return ans;
}
nice
hay Sourav, i am getting some confusion..can you please help me to clear my doubt in this questions
@@nitintayal3928 watch videos again, practice to build recursion tree by urself. You will get ur logic.
@sourav singh i did .but i still getting confusions with other solutions of same question and with your solution also
why we are not following pick and not pick here and have multiple options to pick from . In previous problems we either pick or not pick an element and then move forward
I have the same doubt. Did you get any answer?
transform the initial array to only contain unique elements, and modify the code of combination sum I to always increment index, that'd also solve this problem
You are wrong. If our array is [1,2,,1] and target is 2. Then your solution will only give ans = {2}. But correct answer should be {{1,1,},{2}}
Why looping from index to n-1 is not considered for time complexity? please explain
This seems like a perfect DP problem where there is lot many recursion repetition.
still confused why we did i>ind..i understood arr[i]==arr[i-1] to avoid repetition of same element.
because for i=0 , what will be arr[i-1] , it will be arr[-1] right...which doesn't exist
@@KapilYadavdtukuch bhi
After Watching till 10 minutes, I was able to solve myself. Thanks
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
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?
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
superb!! how smoothly he explained
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
Kadak explanation
I think time complexity should be O(2^ n * k * n log n) because he mentioned in the video that the array must be sorted. Do correct me if I'm wrong
it'll be O(2^ n * k + n log n) as we're sorting array only once, before calling recursion
@@vaibhav7076 yes correct
okey but looping here rgt ? so T.C will be n! rgt ?